fudq's AC Road

先在区间 [0, m]里面找最小的数，对应的下标标号i；接着找区间 [i+1,m++]里面的最小数，对于下标为ii；接着找区间 [ii+1,m++]里面的最小数……这样就会找到n-m个数了。区间这样安排的目的是为了保证取出来的数的顺序。

/*
 * pro.cpp
 *
 *  Created on: 2013-08-21
 *      Author: fudq
 */
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=1010;
const int M=32010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const double eps=1e-7;
const double PI=acos(-1.0);

inline int sign(double x){return (x>eps)-(x<-eps);}
template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
template<class T> inline T Min(T a,T b){return a<b?a:b;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
/*************************/

char s[N];
int n,tot,f[N],ans[N],rmq_n[N][32];

int check(int i,int j)
{
    return f[i]<=f[j]?i:j;
}

void rmq_init(int arr[],int n)
{
    int i,j;
    for(i=1;i<=n;i++)
        rmq_n[i][0]=i;
    for(j=1;(1<<j)<=n;j++)
        for(i=1;i+(1<<j)-1<=n;i++)
        	rmq_n[i][j]=check(rmq_n[i][j-1],rmq_n[i+(1<<(j-1))][j-1]);
}

int rmq(int a,int b)
{
    int m=int(log(b-a+1.0)/log(2.0));
    int x=check(rmq_n[a][m],rmq_n[b-(1<<m)+1][m]);
    return x;
}

void solve()
{
	int len=(int)strlen(s);
	for(int i=0;i<len;i++)
		f[i+1]=s[i]-'0';
	rmq_init(f,len);

	int lef,rig;
	tot=0;lef=1;rig=n+1;
	while(tot < len-n)
	{
		int t=rmq(lef,rig);
		ans[tot++]=f[t];
		lef=t+1;rig++;
	}
	int p=0;
	while(ans[p] == 0 && p<tot)
		p++;
	if(p == tot)
		printf("0");
	for(int i=p;i<tot;i++)
		printf("%d",ans[i]);
	printf("\n");
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("testin.txt","r",stdin);
    //freopen("testout.txt","w",stdout);
#endif
    while(scanf("%s %d",s,&n)!=EOF)
    	solve();
    return 0;
}