摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法: Greedy (遞迴版)

優化輸出 putchar(N+48);代替 printf("%d",N); 0≦N≦9

錯誤的版本不管有沒有優化,都會TLE

/************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char s[35867525];
void Greedy (int now,int start,int end,int need)
{
    if(now==-1||need==0) return;
    int a,last=start-1;
    for(a=start;a<=end;a++)
          if(s[a]-48==now)
             {
                if((end-a)<need)
                   {
                     Greedy (now-1,last+1,a-1,need-(end-a)-1);
                     putchar(now+48);
                     need=end-a;
                     last=a;
                   }
                else
                   {
                      putchar(now+48);
                      last=a;
                      need--;
                   }  
                if(need==0) return;
             }
    if(need!=0)  Greedy (now-1,last+1,end,need);
}
main()
{
  int n;
  while(scanf("%s %d",s,&n)==2)
      {
          Greedy (9,0,strlen(s)-1,n);
          printf("\n");
      }
 return 0;
}

/**********************************************************/

以下是WA版

#include<stdio.h>     
#include<stdlib.h>     
#include<string.h>     
char x[1830000];     
int main()     
{     
 int n;     
 while(scanf("%s %d",x,&n)==2)     
 {     
  /*greddy*/    
  int a,b,c=n,m=strlen(x);     
  int set=-1;     
   for(a=0;a<c;a++)     
    {     
     int max=0;     
     for(b=set+1;b<=m-n;b++)     
      {     
       if(x[b]-48>max)     
        {     
         max=x[b]-48;     
         set=b;     
        }     
      }     
      printf("%d",max);     
      n--;     
    }     
    printf("\n");     
 }     
 return 0;     
}