HDU - 3183 A Magic Lamp (RMQ + 貪心）

​​HDU - 3183 A Magic Lamp​​

題目

分析

#include <bits/stdc++.h>
#define d(x) cout << (x) << endl;
using namespace std;
const int N = 1e4 + 10;

string a;
int num[N];
int st[N][20];
int n, m;

void rmq()          // 預處理最小值下标
{
    for (int i = 1; i <= m; i++){
        st[i][0] = i;
    }
    for (int j = 1; (1<<j) <= m; j++){
        for(int i = 1; i + (1<<j)-1 <= m; i++){
            int a = st[i][j - 1];
            int b = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = num[a] <= num[b] ? a : b;
        }
    }
}

int ask(int l, int r)       //查詢
{
    int k = log2(r - l + 1);
    int a = st[l][k];
    int b = st[r - (1 << k) + 1][k];
    return num[a] <= num[b] ? a : b; // 相同時，優先左邊的
}

void solve()                 
{
    int s = 1;          // 每次查詢左端點
    int e = n + 1;      // 每次查詢右端點
    int k = m - n;      // 查詢次數
    int flag = 0;       //  前導零
    while(k--){
        int t = ask(s, e);
        if(flag || num[t]){
            cout << num[t];
            flag = 1;
        }
        s = t+1;            //  更新左端點
        e++;                //  更新右端點
    }
    if(!flag){
        cout << "0";
    }
    cout << endl;
}

int main()
{
    while(cin >> a >> n){
        m = a.length();
        for(int i = 0; i < m; i++){
            num[i + 1] = a[i] - '0';
        }
        rmq();
        solve();
    }
    return 0;
}