【算法系列学习】HDU 5527 Too Rich贪心

http://www.cnblogs.com/AOQNRMGYXLMV/p/4934747.html
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 
  5 using namespace std;
  6 const int maxn=12;
  7 const int inf=0x3f3f3f3f;
  8 int a[maxn];
  9 int b[maxn];
 10 int val[]={1,5,10,20,50,100,200,500,1000,2000};
 11 int Solve(int t)
 12 {
 13     int ans=0;
 14     for(int i=9;i>=0;i--)
 15     {
 16         if(i==4||i==7)
 17         {
 18             int cnt=min(t/(val[i]*2),b[i]/2);
 19             ans+=cnt*2;
 20             t-=val[i]*2*cnt;
 21         }
 22         else
 23         {
 24             int cnt=min(t/val[i],b[i]);
 25             ans+=cnt;
 26             t-=val[i]*cnt;
 27          } 
 28         if(t==0)
 29         {
 30             break;
 31          } 
 32     }
 33     if(t==0)
 34     {
 35         return ans;
 36     }
 37     else
 38     {
 39         return inf;
 40     }
 41 }
 42 int main()
 43 {
 44     int T;
 45     scanf("%d",&T);
 46     while(T--)
 47     {
 48         int p;
 49         scanf("%d",&p);
 50         int tot=0;
 51         int sum=0;
 52         for(int i=0;i<10;i++)
 53         {
 54             scanf("%d",&a[i]);
 55             tot+=a[i];
 56             sum+=val[i]*a[i];
 57         }
 58         if(sum<p)
 59         {
 60             printf("-1
");
 61             continue;
 62         }
 63         p=sum-p;
 64         int ans=inf;
 65         for(int i=0;i<2;i++)
 66         {
 67             for(int k=0;k<2;k++)
 68             {
 69                 int temp=p;
 70                 memcpy(b,a,sizeof(a));
 71                 if(i)
 72                 {
 73                     if(b[4])
 74                     {
 75                         temp-=val[4];
 76                         b[4]--;
 77                     }
 78                     else
 79                     {
 80                         continue;
 81                     }
 82                 }
 83                 if(k)
 84                 {
 85                     if(b[7])
 86                     {
 87                         temp-=val[7];
 88                         b[7]--;
 89                     }
 90                     else
 91                     {
 92                         continue;
 93                     }
 94                 }
 95                 if(temp>=0)
 96                 {
 97                     ans=min(ans,Solve(temp)+i+k);
 98                 }
 99             }    
100         }
101         if(ans==inf)
102         {
103             printf("-1
");
104          } 
105          else
106          {
107              printf("%d
",tot-ans);
108          }
109     }
110     return 0;    
111 }
View Code
考虑问题的反面，求最大转化为求剩余的最小。然后从大到小贪心，能多用大面值的尽量多用。特判20,50；200,500