原题: http://acm.nyist.net/JudgeOnline/problem.php?pid=448
//nyoj 448 //贪心:结果的每一位都要尽可能地大，这里只是我们搜索的范围受到m限制，因为我们要保证最后的结果有足够的位数。 // 我们可以知道最后结果的位数，每次在限制的范围内寻找最大的数即可。 #include<iostream> #include<cstdio> #include<string> using namespace std; int strlen(char str[101]) { int i=0; while(str[i]!='\0') { i++; } return i; } int main() { int t; scanf("%d",&t); char str[101];//原字符串 char rs[101];//结果字符串 while(t--) { int k; getchar(); scanf("%s",str); scanf("%d",&k); int len=strlen(str); int rest=len-k;//每一次寻找都要保证最后留有足够的位数凑成rest-1位 int pos=0; int now=0; while(rest) { int pp=now;//当前位置 char tmp=str[now]; for(int i=pp+1;i<=len-rest;i++)//在限制范围内寻找最大的数 { if(str[i]>tmp) { tmp=str[i]; pp=i; } } rs[pos++]=str[pp];//放进结果 rest--;//剩余数减一 now=pp+1;//位数后移 } rs[pos]='\0'; printf("%s\n",rs); } return 0; }