数中的最大数.cpp

来自「五种排序算法」· C++ 代码 · 共 66 行

#include <iostream>
#include <cstring> 
using namespace std;
const int N=1000*1000*10 +1;
char buf[N],ans;
int main()
{
    int k;
    while(scanf(" %s%d", buf, &k)!=EOF)
    {
        int len=strlen(buf),rem=len-k,lb=0,ub=0,cnt=1;
        if(rem<=0)
        {
            puts("0");
            continue;
        }
        else if(rem==len)
        {
            puts(buf);
            continue;
        }
        //结果中的第一位必然在buf[k]之前, 因为只能删除k位,
        //所以0~k位中必有一位保留下来了.显然我们要保留
        //0~k位中最小的那位
        ans=buf[0];
        for(int j=1; j<=k; j++)
        {
            if(('0'!=buf[j]||rem==1)&&ans>buf[j])
            {
                ans=buf[j];
                lb=j;
            }
        }
        putchar(ans);
        int digit[10]={},i=lb+1;
        ub=k+cnt;
        while(cnt<rem)
        {
            //计算其余各位,
            for(; i<=ub; i++)
            {
                digit[buf[i]-'0']++;
            }
            for(i=0; i<10; i++)
            {
                if(digit[i])
                {
                    putchar('0'+i);
                    break;
                }
            }
            cnt++;
            int j=lb+1;
            for(;buf[j]-'0'!=i;j++)
                digit[buf[j]-'0']--;
            digit[i]--;
            lb=j;
            i=ub+1;
            ub=k+cnt;
        }
        putchar('\n');
    }
    return 0;
}