這是一道貪心的題目

首先要注意的是計算最多硬幣數及逆向計算留下的錢的最少硬幣數

還有要枚舉50和500這兩個例外的奇偶性

調試時要注意

　　1 既然已經枚舉了，取的時候一定要取偶數個

　　2 計算總數量的時候一定要加上自己已經取得數目

　　3 int 和long long不影響本題的結果

　　4 枚舉的時候一定要判斷能否取出一枚50或500的硬幣

　　5 可能有一些枚舉情況無解，這時要返回inf

　　6 即使在取出錢數小于等于總錢數的情況下，也會有無解，這時一定要判斷

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int inf=999999999; inline int read(){int x=0,f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } inline int min(int x,int y){return x<y?x:y; } int a[10]; int id[10]={1,5,10,20,50,100,200,500,1000,2000}; int flag; inline int cal(int x){int res=0;for(int i=9;i>=0;i--){int num=min(a[i],x/id[i]);x-=num*id[i];if(i==4||i==7) num<<=1;res+=num;}if(x) return inf;return res; } int main(){int T=read();while(T--){int p=read(),sum=0,cnt=0;for(int i=0;i<10;i++) a[i]=read(),sum+=a[i]*id[i],cnt+=a[i];if(p>sum){puts("-1");continue;}if(p==sum){printf("%d\n",cnt);continue;}// cout<<id[4]<<"\t"<<id[7]<<endl;p=sum-p;id[4]=100;id[7]=1000;// cout<<p<<endl;int ans,num1,num2;num1=a[4];num2=a[7];a[4]>>=1;a[7]>>=1;ans=cal(p);a[4]=num1;a[7]=num2;if(p>=50&&a[4]){p-=50;a[4]--;num1=a[4];num2=a[7];a[4]>>=1;a[7]>>=1;ans=min(ans,cal(p)+1);a[4]=num1;a[7]=num2;p+=50;a[4]++;}if(p>=500&&a[7]){p-=500;a[7]--;num1=a[4];num2=a[7];a[4]>>=1;a[7]>>=1;ans=min(ans,cal(p)+1);a[4]=num1;a[7]=num2;p+=500;a[7]++;}if(p>=550&&a[4]&&a[7]){p-=550;a[4]--;a[7]--;a[4]>>=1;a[7]>>=1;ans=min(ans,cal(p)+2);}id[4]=50;id[7]=500;if(ans==inf) puts("-1");else printf("%d\n",cnt-ans);}return 0; }

　　

轉載于:https://www.cnblogs.com/gcyyzf/p/9695737.html

總結

以上是生活随笔為你收集整理的HDU 5527的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。