【bzoj1685】[Usaco2005 Oct]Allowance 津贴

2014年8月2日1,9831

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

Sample Output

111
样例说明
约翰想要每周付给贝茜6美分.他有1个10美分的硬币、100个1美分的硬币、120个5美分的硬币.约翰可以第一周付给贝茜一个10美分的硬币,接着的10周每周付给贝茜2个5芙分硬币,接下来的100周每周付给贝茜一个1美分的硬币和1个5美分的硬币.共计111周.

题解

其实这题数据范围很小T T

tyvj题解:贪心思路就是每次都尽量使FJ花的冤枉钱最少……
所以,先从大到小给硬币,保证绝对不会给多
如果这样选不够数,就再选一个最小的硬币塞给它!
另外注意,不要选好一种给硬币的方案就拼命刷到底,放心吧不会爆的

 

  • cgh2016年11月15日 上午9:09 回复

    为什么我看不懂最后一句

    #1