POJ 3040Allowance(贪心好题目) - c++编程基础

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

Sample Output

如上面的实例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