ACM 11491 11491 - Erasing and Winning
作法 : Greedy
/*********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char s[100001];
void Greedy (int now,int start,int end,int need)
{
if(now==-1||need==0) return;
int a,last=start-1; /*start-1 是可能之間都沒有該數字...*/
for(a=start;a<=end;a++) /*在之間取需要的個數*/
if(s[a]-48==now)
{
if((end-a)>=need)
{
putchar(now+48);
last=a; /*紀錄上一次的位子*/
need--; /*需要的個數一直減少*/
if(need==0) return;
}
else /* 若無法在剩餘的數字中取到足夠的個數 則在上一次出現的位子中取數 */
{
Greedy (now-1,last+1,a-1,need-(end-a)-1); /*不足的往數字(now-1) 從上一次數字(now)出現的位子 到 這個數(now)之前 取不足的數字*/
for(a=a;a<=end;a++)/*退回來之後 輸出剩餘的全部*/
printf("%c",s[a]);
return;
}
}
if(need!=0) Greedy (now-1,last+1,end,need);
/* 取了或者根本沒取 需求不足 則從上一次紀錄的地方往結尾去找 下一個數字(now-1)*/
}
main()
{
int n,m;
while(scanf("%d %d %s",&m,&n,s)==3)
{
if(m==0&&n==0) break;
Greedy (9,0,m-1,m-n);/*先找數字 9*/
printf("\n");
}
return 0;
}