先在区间 [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;
}
评论