| Allowance
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 610 11 1005 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. Source |
贪心思路：
先将面值大于c发给Bessie的钱。 每次从面值最大的开始，用need数组存放每个面值所需要的数目，并且该面值的使用总价值不大于c， 要是不足用小于该面值的补, 但是不大于c。如果c不为零，从最小的面值开始加上，使得损失最小。 如果还有剩余的，说明所剩的金额已经不足以支付下一个月的。 每次使得损失最少，所以总的损失是最小的，所支付的周数最小。#include#include #include #include #include #include #include #define MAX_N 105#define MAX(a, b) ((a > b)? a: b)#define MIN(a, b) ((a < b)? a: b)using namespace std;struct node { int val, num;}mon[MAX_N];bool cmp(node x, node y) { return x.val < y.val;}int need[MAX_N];void init() { for (int i = 0; i < MAX_N; i++) { need[i] = 0; }}int main () { int c, n, m; while (scanf("%d%d", &n, &c) != EOF) { int ans = 0; for (int i = 0; i < n; i++) { scanf("%d%d", &mon[i].val, &mon[i].num); } int m = -1; sort(mon, mon + n, cmp); for (int i = n - 1; i >= 0; i--) { if (mon[i].val >= c) { ans += mon[i].num; } else { m = i; break; } } while (true) { init(); int res = c; //先进行循环，从面值最大的开始求所需 各面值的数目。 for (int i = m; i >= 0; i--) { if (mon[i].num && res) { int k = res/mon[i].val; k = MIN(k, mon[i].num); need[i] = k; res -= k*mon[i].val; } } //如果剩下的大于零，说明不能支付正好的金额，就从最小的面值选一张。 if (res) { for (int i = 0; i <= m; i++) { if (mon[i].val >= res && mon[i].num > need[i]) { res = 0; need[i]++; break; } } } //如果还有剩余，就结束。 if(res) break; int week = 1e8; //找出可以支付的最小的周数 for (int i = 0; i <= m; i++) { if (need[i]) week = MIN(week, mon[i].num/need[i]); } ans += week; for (int i = 0; i <= m; i++) { mon[i].num -= need[i]*week; } } printf("%d\n", ans); } return 0;}/*5 19 69 16 24 01 834*/