题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3183
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> /** rmq 问题：题意很简单，求一行数字中除去其中m个数字，使其组成最小的一个数字 使用rmq解题，设源数字长为n，那么除去m个数字后剩下的还剩n-m个数字，组成最小的数字。 （1）因为剩下n-m个数字，那么在1到m+1位置中最小的那个数字必是结果中的第一个数字i， （2）然后从这个数字i位置的下个位置i+1开始到m+2位置的数字中最小的那个数字必定是 结果中第二个数字，以此类推下去向后找。 （3）为了保证数字最小所以要保证高位最小还要保证数字长度够用~~ **/ char num[1010]; char res[1020]; int dp_min[1010][20]; int t; //返回较小值 int mins(int a,int b) { return num[a]<=num[b]?a:b; } void rmq_init(int len) { for(int i = 0; i < len; i++) dp_min[i][0] = i; for(int j = 1; (1<<j) < len; j++) for(int i = 0; i+(1<<j)-1 < len;i++) dp_min[i][j] = mins(dp_min[i][j-1],dp_min[i+(1<<(j-1))][j-1]); } int query(int l,int r) { int k = (int)(log((double)(r-l+1))/log(2.0)); return mins(dp_min[l][k],dp_min[r-(1<<k)+1][k]); } int main() { int len; while(scanf("%s%d",num,&t)!=EOF) { len = strlen(num); rmq_init(len); int m = len-t; int p = 0,j=0; while(m--) { p=query(p,len-m-1); res[j++] = num[p++]; } for(p = 0; p < j; p++) if(res[p]!='0')break; if(p==j)printf("0"); else { while(p<j) printf("%c",res[p++]); } puts(""); } return 0; }