178543 4 1000001 1 100001 2 12345 2 54321 2
13 1 0 123 321
#include<cstdio>
#include<cstring>
#include<cmath>
char s[1010];
char ans[1020];
int st[1010][20];
int Min(int x,int y)
{
    return s[x] <= s[y] ? x : y;
}
void RMQ_Init(int len)
{
    for(int i = 0; i < len; i++)
    st[i][0] = i;
    for(int j = 1; (1<<j) < len; j++)
    for(int i = 0; i+(1<<j)-1 < len;i++)
    st[i][j] = Min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int Query(int l,int r)
{
    int k = (int)(log((double)(r-l+1))/log(2.0));
    return Min(st[l][k],st[r-(1<<k)+1][k]);
}
int main()
{
    int len, m, i;
    while(scanf("%s%d",s, &m)!=EOF)
    {
        len = strlen(s);
        RMQ_Init(len);
        m = len - m;
        int pos = 0, num = 0;
        while(m--)
        {
            pos = Query(pos, len - m - 1);
            ans[num++] = s[pos++];
        }
        for(i = 0; i < num; i++)
            if(ans[i]!='0')
                break;
        if(i == num)
            printf("0");
        else
        {
            while(i < num)
                printf("%c",ans[i++]);
        }
        puts("");
    }
    return 0;
}#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    string s;
    int m;
    while(cin >> s >> m) {
        int len = s.length(), i, j;
        int p = 0, tmp_pos = m, flag = 0;
        for(i = 0; i < len - m; i++) {
            char mmin = s[p];
            for(j = p + 1; j <= tmp_pos; j++)
            if(s[j] < mmin) {
                mmin = s[j];
                p = j;
            }
            tmp_pos++;
            p++;
            if(!flag) {
                if(mmin == '0')  continue;
                else {
                        cout << mmin;
                        flag = 1;
                }
            }
            else {
                cout << mmin;
            }
        }
        if(!flag)
            cout << "0";
        cout << endl;
    }
    return 0;
}hdu 3183 A Magic Lamp(RMQ),布布扣,bubuko.com
原文:http://blog.csdn.net/lyhvoyage/article/details/38379685