Allowance
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 1039
Accepted: 444
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 ompute the maximum number of weeks he can
pay Bessie.
Input
* Line 1: Two space-separated integers: N and C
* Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John's possession.
Output
* Line 1: A single integer that is the number of weeks Farmer John can pay Bessie at least C allowance
Sample Input
3 6
10 1
1 100
5 120
Sample Output
111
如上面的實例FJ有n種面額的硬幣，每種硬幣的面額排序之後相鄰兩個之間整數倍關系一樣。每種硬幣的數量有nod[i].num個，每周都需要付給傭人至少money金幣，只可以>=，不能少於這個數目。問最多可以給多少周。
首先：
1.nod[i].val>=money，即面額大於等於money，則直接取它的數目即可。
2。依次從大面額到小面額試著取，如果剛好面額之和=money，那就更好了，這個面額可以用小的湊起來，所以選大的合適。
3.如果大的湊不出來相等的，那麼選最大的加起來且
因為是整數倍關系，至少是2倍的關系，比如a[1]=1,a[2]=2,a[3]=4,a[4]=8,那麼每次都是a[i]比a[1]~a[i-1]所有面額之和還大，所以保證了第三種策略的正確性。
題目地址：Allowance
AC代碼：
#include
#include
#include
#include
#include
using namespace std;
int res;
int need[25];
struct node
{
int val;
int num;
}nod[25];
int cmp(node p1,node p2)
{
if(p1.val>=p2.val) return 1;
return 0;
}
int main()
{
int n,money,i,j,t,tmp;
while(cin>>n>>money)
{
for(i=0;i=money面額的
{
if(nod[i].val=t;i--)
if(nod[i].val>=rest&&(nod[i].num-need[i]))
{
need[i]++;
rest=0;
break;
}
if(rest) break;
}
int ans=1e9;
for(i=t;i
