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

79愛的鼓勵 1訂閱站台

greedy

http://www.tcgs.tc.edu.tw/blog/index.php?op=ViewArticle&articleId=7&blogId=2

明明是重新打過,卻測試了1個小時...才對
看來想的不夠詳細

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

#include<stdio.h>  
#include<stdlib.h>  
main()  
{  
 int n;
 int cash[5]={1,5,10,20,50};
 while(scanf("%d",&n)==1)   
  {  
   while(n--)
    {
     int value,t,a,b,c,p[6]={0},sum=0;
     scanf("%d",&value);
     for(a=0;a<5;a++)
      {
       scanf("%d",&t);
       sum=sum+t*(cash[a]);
       p[a]=t;
      }
     for(a=0;a<5;a++)
      {
       scanf("%d",&t);
       p[a]=p[a]+t;
      }
      sum=sum-value;  /*剩下的錢*/
      int m,mm;
      m=sum/cash[4];
      if(m>p[4]) m=p[4];
      int r1=m,r2=m-1;
      sum=sum-cash[4]*m;
      mm=sum+cash[4];    /*特殊情況必須用2種方式,跑greedy*/
      for(a=3;a>=0;a--)
       {
        m=sum/cash[a];
        if(m>p[a])  m=p[a];
          r1=r1+m;
          sum=sum-m*cash[a];
        m=mm/cash[a];
        if(m>p[a]) m=p[a];
          r2=r2+m;
          mm=mm-m*cash[a];
       }
       printf("%d\n",(sum==0)?r1:r2);
    }
  }    
 return 0;  
}