题目来源:http://ac.nbutoj.com/Problem/view.xhtml?id=1181
题意:前面说了一堆废话,就是说给你一个字符串,全部由数字组成,让你在里面删除n个数,最后得到的数越小越好。
思路:此题和NYOJ上的一道题基本上一样,不过NYOJ上让求得是最大数,这里求的是最小数。思路一样,严格来说,这道题数据有点水了,主要是字符串太长,数据变态点的话,我的方法可能会tle。我的思路是不断的选出最小数,选的范围一直改变。具体来说,设pos=0,最后剩下的数的长度为len,字符串的长度为Len,则第一次筛选的范围是从pos到Len-len+1,在这之间选出一个最小的数,并且是pos的值等于这个最小数的位置,len--。这样循环操作,最后找出即可。
代码:
#include <iostream> #include <cstdio> #include <string.h> #include <string> using namespace std; const int N = 120005; int main(){ //freopen("1.txt","r",stdin); string ss; while(cin>>ss){ int k; scanf("%d",&k); int len = ss.size(); int pos = 0,leftlen = len - k,num[N],cnt = 0; while(leftlen > 0){ int mmin = 100; for(int i = pos;i < len-leftlen+1;++i){ if((int)(ss[i]-'0') < mmin){ mmin = (int)(ss[i]-'0'); pos = i; } } leftlen--; pos++; num[cnt++] = mmin; } int kk; for(int i = 0;i < cnt;++i){ if(num[cnt]){ kk = i; break; } } for(int i = kk;i < cnt;++i) printf("%d",num[i]); printf("\n"); } return 0; }