「BZOJ1685」[Usaco2005 Oct] Allowance 津贴
Description
As a reward for record milk production, Farmer John has decided to start paying Bessie the cow a small weekly allowance. FJ has a set of coins in N (1 <= N <= 20) different denominations, where each denomination of coin evenly divides the next-larger denomination (e.g., 1 cent coins, 5 cent coins, 10 cent coins, and 50 cent coins). Using the given set of coins, he would like to pay Bessie at least some given amount of money C (1 <= C <= 100,000,000) every week. Please help him compute the maximum number of weeks he can pay Bessie.
作为对勤勤恳恳工作的贝茜的奖励，约翰已经决定开始支付贝茜一个小的每周津贴． 约翰有n(1≤N≤20)种币值的硬币，面值小的硬币总能整除面值较大的硬币．比如说，币值有如下几种：1美分，5美分，10美分，50美分…．．
利用给定的这些硬币，他将要每周付给贝茜一定金额的津贴C(1≤C≤10^8)．
请帮他计算出他最多能给贝茜发几周的津贴．
Input
第1行：2个用空格隔开的整数n和C.
第2到n+1行：每行两个整数表示一种币值的硬币．第一个整数V(I≤y≤10^8)，表示币值．
第二个整数B(1≤B≤10^6)，表示约翰拥有的这种硬币的个数．
Output
一个整数，表示约翰付给贝茜津贴得最多的周数．
Sample Input
3 6
10 1
1 1 00
5 1 20
10 1
1 1 00
5 1 20
Sample Output
111
样例说明
约翰想要每周付给贝茜6美分．他有1个10美分的硬币、100个1美分的硬币、120个5美分的硬币．约翰可以第一周付给贝茜一个10美分的硬币，接着的10周每周付给贝茜2个5芙分硬币，接下来的100周每周付给贝茜一个1美分的硬币和1个5美分的硬币．共计111周．
样例说明
约翰想要每周付给贝茜6美分．他有1个10美分的硬币、100个1美分的硬币、120个5美分的硬币．约翰可以第一周付给贝茜一个10美分的硬币，接着的10周每周付给贝茜2个5芙分硬币，接下来的100周每周付给贝茜一个1美分的硬币和1个5美分的硬币．共计111周．
题解
其实这题数据范围很小T T
JoyOI题解：贪心思路就是每次都尽量使FJ花的冤枉钱最少……
所以，先从大到小给硬币，保证绝对不会给多
如果这样选不够数，就再选一个最小的硬币塞给它！
另外注意，不要选好一种给硬币的方案就拼命刷到底，放心吧不会爆的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int l=1,r,m,ans; struct data{int v,b;}a[25]; inline bool operator<(data a,data b) { return a.v<b.v; } bool solve() { int sum=0; for(int i=r;i>=l;i--) { int t=(m-sum)/a[i].v; t=min(t,a[i].b); sum+=a[i].v*t;a[i].b-=t; if(m==sum)break; } if(m==sum)return 1; while(!a[l].b&&l<=r)l++; while(!a[r].b&&l<=r)r--; if(l>r)return 0; while(sum<m) { int t=(m-sum)/a[l].v+1; t=min(t,a[l].b); sum+=a[l].v*t;a[l].b-=t; if(!a[l].b)l++; if(l>r)break; } if(sum<m)return 0; return 1; } int main() { r=read();m=read(); for(int i=1;i<=r;i++) a[i].v=read(),a[i].b=read(); sort(a+1,a+r+1); while(a[r].v>=m&&l<=r){ans+=a[r].b;r--;} while(solve())ans++; printf("%d\n",ans); return 0; } |
计数器 9861693
OI 课件=>
OI 课件=>
为什么我看不懂最后一句