Allowance

Time Limit: 1000MS Memory Limit: 65536K

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
Hint

INPUT DETAILS:

FJ would like to pay Bessie 6 cents per week. He has 100 1-cent coins,120 5-cent coins, and 1 10-cent coin.

OUTPUT DETAILS:

FJ can overpay Bessie with the one 10-cent coin for 1 week, then pay Bessie two 5-cent coins for 10 weeks and then pay Bessie one 1-cent coin and one 5-cent coin for 100 weeks.

思路:

本题就是要用原有的钱,尽量多的付工资,所以假如钞票的数额大于需要的工资,那么一张钞票就是一周的工资,当数额小于的时候,那么就先从最大的开始遍历,尽量将工资凑满,也就是不要由多余的钱凑出,知道最后没有办法刚刚好付工资后,就将超过数额的钞票组合成的也给出工资。

#include <iostream>
#include <algorithm>
using namespace std;
struct NODE {
	int v;
	int b;
};
NODE node[50];
bool cmp(NODE a, NODE b) {
	return a.v > b.v;
}
int main() {
	int n, m, x, y;
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> node[i].v >> node[i].b;
	sort(node, node + n, cmp);
	int week = 0;
	for (int i = 0; i < n; i++) {
		if (node[i].v >= m) {
			week += node[i].b;
			node[i].b = 0;
		}
		else break;
	}
	while (1) {
		int use[50] = {0}; //用来存储花的钱的数量 
		bool book = false;
		int money = m;
		for (int i = 0; i < n; i++) {
			if (node[i].b > 0) {
				int use[i] = min(money / node[i].v, node[i].b);
				money -= use[i] * node[i].v; //剩下的钱还需要支付的钱 
				if (money == 0) { //凑齐工资 
					book = true;
					break;
				}
			}
		}
		if (money > 0) {
			for (int i = n - 1; i >= 0; i--) { //从小到大取
				if (use[i] < node[i].b) { //这个面额的钱的数量要大于使用的数量 
					while (use[i] < node[i].b) { //直到将最小的那个用完 
						money -= node[i].v; //将不够的钱补上 
						use[i]++; //使用的钱的数量增加 
						if (money < 0) { //凑齐工资 
							book = true;
							break; 
						} 
					}
				} 
				if (book) break;
			} 
		}
		if (!book) break; 
		int minn = 0x7fffffff;
		for (int i = n - 1; i >= 0; i--) { //记录最小的支付数
			if (use[i] > 0) minn = min(minn, node[i].b / use[i]);
		}
        for (int i = n - 1; i >= 0; i--) { //从硬币总数量中减去支付数
            if (use[i] > 0) node[i].b -= minn * use[i];
        }
        week += minn;
    }
	cout << week << endl; 
	return 0; 
}