零花钱

1263: 零用钱

时间限制: 1 Sec 内存限制: 128 MB
作为创造销售纪录的回报，Farmer John决定开始每个星期给Bessie一点零花钱。 FJ有一些硬币，一共有N (1 < = N < = 20)种不同的面额。每一个面额都能整除所有比它大的面额。 他想用给定的硬币的集合，每个星期至少给Bessie某个零花钱的数目C (1 < = C < = 100000000)。请帮他计算他最多能支付多少个星期的零花钱。
输入
第1行: 两个由空格隔开的整数: N 和 C

第2到第N+1行: 每一行有两个整数表示一个面额的硬币：

硬币面额V (1 < = V < = 100,000,000)

和Farmer John拥有的该面额的硬币数B (1 < = B < = 1,000,000).
输出
输出一行： 一个单独的整数，表示FJ 最多能给Bessie支付多少个星期至少为C的零用钱。
样例输入
3 6
10 1
1 100
5 120
样例输出
111

#include<stdio.h>
#include<algorithm>
using namespace std;
struct Money {   
 int The_price;    
 int The_number;
 };
 int cmp(Money a,Money b) {    
 return a.The_price<b.The_price;
 }
int main() {    
  int N,C,sum=0,num;    
  bool judge=true;    
  scanf("%d %d",&N,&C);    
  struct Money money[N];    
  for(int i=0; i<N; i++)       
     scanf("%d %d",&money[i].The_price,&money[i].The_number);    
  sort(money,money+N, cmp);
  for(num=N-1; num>=0; num--)
         if(money[num].The_price>=C) 
              sum+=money[num].The_number; 
         else break;    
  while(judge) {      
       judge=false;    
       int t=C;     
        for(int i=num; i>=0; i--) {
               while(t>money[i].The_price&&money[i].The_number>0) { 
                        t-=money[i].The_price; 
                        money[i].The_number--; 
               }       
         }        
      for(int i=0; i<=num; i++) {
                  while(t>0&&money[i].The_number>0) { 
                                 t-=money[i].The_price;                
                                 money[i].The_number--;            
                  }
        }        
        if(t<=0) { 
                   judge=true;           
                   sum++;        
                   }     
    }    
            printf("%d\n",sum);
  }