A Magic Lamp
给出长度不超过1000个数字的数，删除n个数使剩下来的数最小。
思路参考：Codeforce101061E-Playing with numbers(RMQ-ST)
#include<bits/stdc++.h>
using namespace std;
int dpminx[1100][26];
char s[1100];
queue<char>qu;
int n;
int finminx(int x,int y)
{
if(s[x]<=s[y])
{
return x;
}
else
{
return y;
}
}
void ST(int n)
{
for(int i=0;i<n;i++)
{
dpminx[i][0]=i;
}
for(int j=1;j<=26;j++)
{
for(int i=0;i+(1<<j)-1<n;i++)
{
dpminx[i][j]=finminx(dpminx[i][j-1],dpminx[i+(1<<(j-1))][j-1]);
}
}
}
int queryminx(int i,int j)
{
int k=log2(j-i+1.0);
return finminx(dpminx[i][k],dpminx[j-(1<<k)+1][k]);
}
int main( )
{
while(~scanf("%s %d",&s,&n))
{
//cout<<s<<endl;
while(!qu.empty( ))
{
qu.pop( );
}
int len=strlen(s);
ST(len);
int x=len-n;
int tem=0,tep=n;
for(int i=1;i<=x;i++)
{
tem=queryminx(tem,tep);
qu.push(s[tem]);
tep++;
tem++;
}
int flag=0;
while(!qu.empty( ))
{
if(qu.front( )=='0'&&flag==0)
{
qu.pop( );
continue;
}
else
{
cout<<qu.front( );
qu.pop( );
flag=1;
}
}
if(flag==0)
{
cout<<0;
}
cout<<endl;
}
return 0;
}
