24h購物| | PChome| 登入
2009-11-07 23:02:14| 人氣1,129| 回應0 | 上一篇 | 下一篇

ACM 11491 11491 - Erasing and Winning

推薦 0 收藏 0 轉貼0 訂閱站台

作法 : 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;  

台長: 來源不明
人氣(1,129) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 數位資訊(科技、網路、通訊、家電) | 個人分類: ACM |
此分類下一篇:ACM 536 Tree Recovery
此分類上一篇:ACM 11572 11572 - Unique Snowflakes

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文