<题目链接>
<转载于 >>> >
题目大意：
给出一个长度不超过1000位的数，求删去m位数字以后形成的最小的数字是多少。
解题分析：
分析：我们可以把题目转化为这样一个模型：从A[1]、A[2]、……、A[n] n个数中选出n-m个数，使得组成的数最小。
一、使用RMQ，设原数字长为n，那么除去m个数字后还剩n-m个数字。 下面的(一)、(二)用到了抽屉原理
（1）因为有n-m个数字，那么在0到m-1位置中最小的那个数字必是结果中的第一个数字，记录其位置为pos
（2）然后从这个位置的下个位置pos+1开始到m+2位置的数字中最小的那个数字必定是结果中第二个数字，以此类推下去向后找。
（3）为了保证数字最小,所以要保证高位最小,还要保证数字长度满足条件。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std; const int M = 1e3+;
char s[M];
char ans[M];
int st[M][],m;
int Min(int a,int b){ //根据它们在字符串中的值，返回值更小的元素的下标
return s[a]<=s[b]?a:b;
}
void RMQ_init(int len){ //用ST表预处理[i,i+2^J-1]这个区间内最小值所在的坐标
for(int i=;i<len;i++)
st[i][]=i;
for(int j=;(<<j)<len;j++)
for(int i=;i+(<<j)-<len;i++)
st[i][j]=Min(st[i][j-],st[i+(<<(j-))][j-]);
}
int RMQ(int l,int r){ //查询该区间内最小值的下标
int k=log((double)(r-l+))/log(2.0);
return Min(st[l][k],st[r-(<<k)+][k]);
}
int main(){
while(scanf("%s%d",&s,&m)!=EOF){
int len=strlen(s);
RMQ_init(len);
m=len-m; //m此时代表着从该字符串中按顺序选出的字符数,使得该选出的字符最小
int loc=,num=;
while(m--){
loc=RMQ(loc,len-m-); //不断在[loc,len-m-1]这个变化的区间内选最小值,因为该字符串首地址是0，所以要-1
ans[num++]=s[loc++];
}
int cur;
for(cur=;cur<num;cur++) //处理前导0
if(ans[cur]!='')break;
if(cur==num)puts("");
else{
for(;cur<num;cur++)printf("%c",ans[cur]);
printf("\n");
}
}
return ;
}
2018-10-20