题目内容：
从一个n位数字的整数中删除m位数字，要求余下的数字在 不改变顺序的情况下，表示的值最小。 请神灯帮你。 输入描述 整数n m, 可能有多个测试用例。 n<=1000 输出描述 余下的整数数。如果整数前面是0，不用输出. 输入样例 178543 4 1000001 1 100001 2 12345 2 54321 2 输出样例 13 1 0 123 321
解题思路
0 1 2 3 4 5 6 7 8 9 A={3 2 4 5 6 8 1 2 9 7}, 用一个稀疏的二维表D,定义 3245681297 D[i,j]=max(A[i]:A[i+2^j-1])，加上A[i]共2^(j-1)个 由于D[i,j]=max(D[i,j-1],D[i+2^(j-1),j-1])
即max(A[i:i+2^(j-1)]),max(A[i+2^(j-1):i+2^(j-1)+2^(j-1)]) D[0,2]=max(maxA[0:4],maxA[4:8]) D[i,1]= max(D[i,0], D[i+1,0]),区间跨度为2^1=2,即a[0:2] D[i,2]= max(D[i,1], D[i+2,1]),区间跨度为 故可以用动态规划填表， 先填第0列D[i,0]=A[i]，后面第j列用到第j-1列的数据。 D不用填满，第i行要填log(n-i)个元素，一共要填sum(log(i))<nlog(n)个元素（预处理时间）。
本题思路：在n个位里面删除m个位，也就是找出n-m个位组成最小数 所以在区间 [0, m]里面找最小的数，对应的下标标号i 接着找区间 [i+1,m++]里面的最小数，对于下标为ii 接着找区间 [ii+1,m++]里面的最小数…… m+(n-m-1):n-1 这样就会找n-m个数了。区间这样安排的目的是为了保证取出来的数的顺序。 就是说，分成n-m个区间，找出的n-m个数一定是总区间里最小的
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 10005
#define INF 0x3f3f3f
using namespace std;
char a[N];
int x[N];
int y[N];//存结果
int dp[N][20];
int n,m;
void print_table(int dp[][20],int n){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
printf("%d ",x[dp[i][j]]);
printf("\n");
}
}
void print_index_table(int dp[][20],int n){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
printf("%d ",dp[i][j]);
printf("\n");
}
}
int RMQ_ST(int* x,int n){//存最小值在x[]里的下标
//初始化dp[][]
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dp[i][j]=-1;
int k=floor(log2(n));
//cout<<"k="<<k<<endl;
for(int i=0;i<n;i++)
dp[i][0]=i;//x[i]的下标i
for(int j=1;j<=k;j++){
int m=n-(1<<j);//如j=3,后面空7个,0:n-2^3=10-8=2
//1<<j,表示1乘以j个2,即2^j
//cout<<"j:"<<j<<" imax=n-2^j:"<<m<<endl;
for(int i=0;i<=m;i++){
int len=1<<(j-1);//两个子区间长度
if(x[dp[i][j-1]]<=x[dp[i+len][j-1]])//相等取下标小的那个
dp[i][j]=dp[i][j-1];
else dp[i][j]=dp[i+len][j-1];
//cout<<"i:"<<i<<" i+1<<(j-1):"<<(i+len)<<endl;
//dp[0][1]=max(dp[0][0],dp[1][0]),2个,所以dp[i][j]:max(a[i:i+2^j-1])，dp[0][1]=max(a[0:0+2^1-1])
//dp[0][2]=max(dp[0][1],dp[2][1])
}
}
//填表完成
int l=0,r=n-1;
int ans;
if(x[dp[l][k]]<=x[dp[r-(1<<k)+1][k]])
ans=dp[l][k];
else ans=dp[r-(1<<k)+1][k];
return ans;//r-(2^k)+1:r-(2^k)+1+2^k-1
}
int RMQ(int dp[][20],int n,int l,int r){
//int k=floor(log2(n));//错误
int k=floor(log2(r-l+1));// 正确，搞清楚why
int ans;
if(x[dp[l][k]]<=x[dp[r-(1<<k)+1][k]])
ans=dp[l][k];
else ans=dp[r-(1<<k)+1][k];
return ans;
}
void solve(int *x,int n,int m){
memset(y,-1,sizeof(y));
RMQ_ST(x,n);
//print_table(dp,n);
//print_index_table(dp,n);
int min_index=-1,tmp_m=m;
for(int i=0;i<n-m;i++){
int tmp_index=min_index;
min_index=RMQ(dp,n,min_index+1,tmp_m);
/*for(int j=0;j<i;j++)
if(y[i]==min_dex)
break;*/
y[i]=min_index; //存的是下标就不用考虑数相同的情况了吗？？
//printf("min(x[%d:%d])=%d min_index=%d\n",tmp_index+1,tmp_m,x[min_index],y[i]);
//取到很多下标为-1的情况
tmp_m++;
}
}
int main(){
cout<<"3"<<endl;
while(~scanf("%s%d",a,&m)){
int n=strlen(a);
//cout<<"n:"<<n<<" m:"<<m<<endl;
if(m>n)
printf("0");
else{
for(int i=0;i<n;i++)
x[i]=a[i]-'0';
solve(x,n,m);
//输出结果
/*printf("y[]:\n");
for(int i=0;i<n-m;i++)printf("%d ",y[i]);printf("\n");
for(int i=0;i<n-m;i++)printf("%d ",x[y[i]]);printf("\n");*/
//1 2 3 4 5 6
//0 0 0 0 0 1
//0 1 2 3 4 5
int i;
for(i=0;i<n-m;)//n==7,m==1,,n-m==6,当i==5时退出
if(x[y[i]]==0)
i++;
else break;
if(i==n-m)printf("0",i);//i==6时退出结果才为0
else
for(;i<n-m;i++)
printf("%d",x[y[i]]);
}
printf("\n");
}
return 0;
}
