A magic lamp
时间限制：1秒 内存限制：128M
题目描述
kiki喜欢旅行。 有一天她发现了一盏神灯，可惜神灯里的精灵并不那么善良。 kiki必须回答一个问题，然后精灵才能实现她的一个梦想。
问题是：给你一个整数，你可以精确地删除
m位数字。 剩余的数字将形成一个新的整数。 你应该把它减到最小,并且不允许更改数字顺序。 现在你能帮助kiki实现她的梦想吗？
输入描述
有若干组测试用例。
每个测试用例将包含一个给定的整数（最多可以包含
1100 位数字。）和整数
m（如果整数包含
n 位数字，则
m 不会大于 n）。
给定的整数将不包含前导零。
输出描述
对于每种情况，在一行中输出您可以获得的最小结果。
如果结果包含前导零，则忽略它。
样例输入
178543 4
1000001 1
100001 2
12345 2
54321 2
样例输出
13
1
0
123
321
神经码风，勿喷，谢
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
int m;
pair<int,int>dpmin[1105][11],a[1105];
char s[1105];
queue<int>q;
pair<int,int> ask(int i,int j){
pair<int,int>pp=dpmin[i][j-1].first>dpmin[i+(1<<(j-1))][j-1].first?dpmin[i+(1<<(j-1))][j-1]:dpmin[i][j-1];
return pp;
}
pair<int,int> ask2(int l,int r,int k){
pair<int,int>pp=dpmin[l][k].first>dpmin[r-(1<<k)+1][k].first?dpmin[r-(1<<k)+1][k]:dpmin[l][k];
return pp;
}
int main(){
while(scanf("%s %d",s,&m)!=EOF){
int n=strlen(s);
for(int i=1;i<=n;i++) dpmin[i][0].first=s[i-1]-'0',dpmin[i][0].second=i;
int x=log2(n);
for(int j=1;j<=x;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
pair<int,int>x=ask(i,j);
dpmin[i][j]=x;
}
}
int pos=n-m,l=1,r=m+1;
while(pos--){
int k=log2(m+1);
q.push(min(dpmin[l][k].first,dpmin[r-(1<<k)+1][k].first));
pair<int,int>x=ask2(l,r,k);
m-=(x.second-l);
l=x.second+1;
r=l+m;
}
while(!q.empty()&&!q.front()) q.pop();
if(q.size()==0) printf("0\n");
else{
while(!q.empty()){
printf("%d",q.front());
q.pop();
}
printf("\n");
}
}
return 0;
}