做题感悟:开始做这题时用了类似动态规划的方法做的,但是后来学习了RMQ算法后,听说可以用它来做,但是这题纠结了很久,就因为取整没处理好。
解题思路:假设数字长度为n,要求删去m个。可以理解为从n个中选n-m 个组成最小的数。那么第一个选入的最小的数一定在 1~m+1 个中选取,假设你在m+2个之后选取那么从m+2 到n 不足n-m个数,如果从1 ~ x( x <= m ),有可能前几位都很大就会成为被删的对象。所以第一个选入的最小数一定在1~m+1 中选。假设在1~m+1 中选取了x位置的数,那么下一次选取就要从x+1 ~ m+2 ,现在相当于从n-x 个数中删除m-x+1 个数,再用上面的方法选第二个数要从x+1~m+2
中选,以此类推……
代码:
#include<stdio.h> #include<iostream> #include<map> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<queue> #include<algorithm> using namespace std ; const int MX = 1005 ; int n ; char s[MX],sx[MX] ; int m[MX][22] ; int min(int x,int y) { return s[x] <= s[y] ? x : y ; // 注意 <= } void pret(int len) { for(int i=1 ;i<=len ;i++) m[i][0]=i-1 ; for(int j=1 ;j!=20 ;j++) for(int i=1 ;i+(1<<j)-1<=len ;i++) m[i][j]=min(m[i][j-1],m[i+(1<<(j-1))][j-1]) ; } int query(int x,int y) { int k=(int)(log(y-x+1.0)/log(2.0)) ; //因为取整后面没加上()错了n次 return min(m[x][k],m[y-(1<<k)+1][k]) ; } int main() { while(~scanf("%s%d",s,&n)) { int len=strlen(s) ; pret(len) ; int x=1,r=0 ; int p=len-n ; while(p--) { int y=query(x,len-p) ; sx[r++]=s[y] ; x=y+2 ; } int i ; for(i=0 ;i<r ;i++) // 去掉前导零 if(sx[i]!='0') break ; if(i==r) printf("0\n") ; else { for( ;i<r ;i++) printf("%c",sx[i]) ; printf("\n") ; } } return 0 ; }