?

　　大致題意：有1到N種硬幣，第i種硬幣的數量為Bi、價值Vi；Farmer John每周要給他的奶牛發至少價值為C的補貼；問利用前面的N種硬幣，最多可以給他的奶牛發多少周的補貼？ ?這是道貪心的題應該不難察覺出來，下面就說下這里貪心的方法： 既然每周發的錢是至少為C，那么用上述硬幣湊出來的價值必須是>=C的； 因為湊出來的價值很可能總是不能剛好等于C的，所以大部分時候給的都是會比C要大一些的，而為了能讓john盡可能多的發多幾周補貼，那就得讓每次發的補貼中"比C多出的那部分"盡可能的小；這樣做即等于 能夠節約更多些錢 來為后面當補貼發。

? 1、將硬幣價值從大到小排序。

? 2、假設前面k種的硬幣價值都是大于等于C的，那么這些就直接取(即一周發一個硬幣)，因為這些是沒辦法節約的了。

? 3、那么用k+1種到第N種都是硬幣價值小于C的了；就從大到小拿 盡可能的多拿，但不能大于C(即假如第i種硬幣所有拿走都還小于C，就把第i種全拿走，然后往后同樣方式判斷第i+1種硬幣， 直至最接近C而又小于C )。

? 4、如果第3步中拿的價值小于C；那就從第k+1種到第N種硬幣中 從小到大拿，也是盡可能的多拿，直到剛好>=C就停止；這樣就使得損失為最小了。

? 5、將這樣取錢方式所能出現的次數 加入到計數器(如果直接一周一周的模擬...可能會超時==...)， 然后返回第3步。

1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<cctype> 7 #include<algorithm> 8 #include<set> 9 #include<map> 10 #include<vector> 11 #include<queue> 12 #include<stack> 13 #include<utility> 14 #define ll long long 15 #define inf 0x3f3f3f3f 16 using namespace std; 17 18 int n,c; 19 typedef struct node 20 { 21 int v,b; 22 } node; 23 node a[25]; 24 bool cmp(node a,node b) 25 { 26 return a.v>b.v; 27 } 28 int cnt; 29 int main() 30 { 31 //freopen("input.txt","r",stdin); 32 scanf("%d%d",&n,&c); 33 for(int i=0; i<n; i++) 34 scanf("%d%d",&a[i].v,&a[i].b); 35 sort(a,a+n,cmp); //按價值從大到小排序 36 // 37 cnt=0; 38 int i; 39 for(i=0;; i++) // 把大于等于c的先全部發完 40 { 41 if(a[i].v>=c) 42 cnt+=a[i].b; 43 else 44 break; 45 } 46 //經過上面的循環,0到i-1種類的硬幣都發完了 47 int need[25]; //標記某一種硬幣用了多少個 48 while(true) 49 { 50 memset(need,0,sizeof(need)); 51 int sum=c; 52 for(int j=i;j<n;j++) 53 { 54 if(a[j].b&&sum>0) 55 { //從大到小取,但不能超過c! 56 need[j]+=min(a[j].b,sum/a[j].v); 57 sum-=a[j].v*need[j]; 58 } 59 } 60 // 61 if(sum>0) 62 { 63 int temp; 64 for(int j=n-1;j>=i;j--) 65 { 66 if(a[j].b&&sum>0) //如果上面那次取法不夠，就從小往大找補替，這樣保證是最小損失 67 { 68 temp=min(a[j].b-need[j],(sum+a[j].v-1)/a[j].v); 69 if(temp>0) 70 { 71 sum-=temp*a[j].v; 72 need[j]+=temp; 73 } 74 } 75 } 76 } 77 if(sum>0) 78 break; //如果還不夠,就直接退出了 79 // 80 int temp=inf; 81 for(int j=i;j<n;j++) 82 { 83 if(need[j]) 84 { //這里取最小的 每次需要的種類的次數; 從而避免用c來每周每周的計算(會超時噠=_=) 85 temp=min(temp,a[j].b/need[j]); 86 } 87 } 88 cnt+=temp; 89 for(int j=i;j<n;j++) 90 { 91 if(need[j]) 92 { //把用了的硬幣刪掉 93 a[j].b-=temp*need[j]; 94 } 95 } 96 } 97 printf("%d\n",cnt); 98 return 0; 99 }

?

轉載于:https://www.cnblogs.com/geek1116/p/5672751.html

總結

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

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