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;
}