題目鏈接：http://begin.lydsy.com/JudgeOnline/problem.php?id=1333

題意：

　　有n種不同幣值的硬幣，并保證大幣值一定是小幣值的倍數。

　　每種硬幣的幣值為val，數量為cnt。

　　每個月你要給Bessie發金額為c的津貼（可以比c多，但不能少）。

　　問你最多能發多少個月。

?

題解：

　　貪心。

?

　　貪心策略：

　　　　（1）如果能恰好湊出c的錢，則應盡可能使用大幣值的硬幣。

　　　　（2）如果不能恰好湊出，則應讓花的冤枉錢盡可能少。

?

　　實現：

　　　　先按幣值從大到小排序。。。

　　　　（1）在保證不花冤枉錢的前提下，盡可能使用大硬幣。

　　　　（2）如果沒湊夠c，則再付一個幣值最小的硬幣。（在第一步之后，再任意給出一個硬幣都會使總付出大于c）

?

AC Code:

1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 #define MAX_N 25 6 7 using namespace std; 8 9 struct Coin 10 { 11 int val; 12 int cnt; 13 Coin(int _val,int _cnt) 14 { 15 val=_val; 16 cnt=_cnt; 17 } 18 Coin(){} 19 friend bool operator < (const Coin &a,const Coin &b) 20 { 21 return a.val>b.val; 22 } 23 }; 24 25 int n,c; 26 int ans=0; 27 Coin coin[MAX_N]; 28 29 bool pay() 30 { 31 int rest=c; 32 for(int i=0;i<n;i++) 33 { 34 int temp=min(coin[i].cnt,rest/coin[i].val); 35 coin[i].cnt-=temp; 36 rest-=temp*coin[i].val; 37 } 38 if(rest==0) return true; 39 for(int i=n-1;i>=0;i--) 40 { 41 if(coin[i].cnt!=0) 42 { 43 coin[i].cnt--; 44 return true; 45 } 46 } 47 return false; 48 } 49 50 int main() 51 { 52 cin>>n>>c; 53 for(int i=0;i<n;i++) 54 { 55 cin>>coin[i].val>>coin[i].cnt; 56 } 57 sort(coin,coin+n); 58 while(pay()) ans++; 59 cout<<ans<<endl; 60 }

?

轉載于:https://www.cnblogs.com/Leohh/p/7565240.html

總結

以上是生活随笔為你收集整理的BZOJ 1685 [Usaco2005 Oct]Allowance 津贴：贪心【给硬币问题】的全部內容，希望文章能夠幫你解決所遇到的問題。

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