一、题目
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.
OutputLine 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.
二、思路&心得
- 贪心题目：从局部最优解得到全局最优解。
- 贪心策略如下：先对数据按照金额从小到大进行排序。对于金额大于C的纸币，直接全部取出；之后进行若干次循环，每次循环中先从大到小尽可能取到小于C的最大金额，之后再从小到大尽可能凑满C，允许超出一个当前最小金额值，一次处理结束后更新相应金额的数量。
这个贪心策略的数学化证明暂时没有想到，题目中还给出“金额之间还有确定的倍数关系”，也不清楚这个信息在算法中具体体现了什么作用。对于这个贪心策略，一个较为直观的解释如下：类比生活中买东西，当消费了一定金额后，我们肯定都是使用尽可能多的大面值的RMB，再使用小面值的，整个题目的思想应该跟这个差不多，我们生活中都下意识使用了很多的贪心策略。
PS：做这个题目时，实在被坑了好久，花了三四个小时，RE + WA无数次才过，主要的问题还是自己一开始上手时，所使用的贪心策略完全错误，尝试了多种，并且举反例证明之后才逐渐找到了正确的贪心策略。
三、代码
#include<cstdio>
#include<climits>
#include<algorithm>
using namespace std;
const int MAX_N = 25;
int N, C;
int ans;
int use[MAX_N];
struct Money {
int value;
int number;
} a[MAX_N];
bool cmp(Money a, Money b) {
return a.value < b.value;
}
void solve() {
int i, start = -1;
int min_num, dist;
//计算所有面额大于C的数据
for (i = N - 1; i >= 0; i --) {
if (a[i].value >= C) {
ans += a[i].number;
} else {
start = i;
break;
}
}
while (1) {
fill(use, use + N, 0);
dist = C;
//从大到小取到小于C的最大数值
for (i = start; i >= 0; i --) {
if (a[i].number) {
min_num = min(dist / a[i].value, a[i].number);
use[i] = min_num;
dist -= a[i].value * min_num;
}
}
//从小到大凑满C
if (dist > 0) {
for (int i = 0; i <= start; i ++) {
if (a[i].number) {
min_num = min((dist + a[i].value - 1) / a[i].value, a[i].number - use[i]);
use[i] += min_num;
dist -= a[i].value * min_num;
if (dist <= 0) break;
}
}
}
if (dist > 0) break;
//数量更新
min_num = INT_MAX;
for (i = 0; i <= start; i ++) {
if (use[i])
min_num = min(min_num, a[i].number / use[i]);
}
for (i = 0; i <= start; i ++) {
if (use[i]) {
a[i].number -= min_num * use[i];
}
}
ans += min_num;
}
printf("%d\n", ans);
}
int main() {
while (~scanf("%d %d", &N, &C)) {
ans = 0;
for (int i = 0; i < N; i ++) {
scanf("%d %d", &a[i].value, &a[i].number);
}
sort(a, a + N, cmp);
solve();
}
return 0;
}