挑战程序设计竞赛 2.2 poj 3040 Allowance 贪心

2023-10-19 16:21 由 itdef 发表于 #其他

https://vjudge.csgrandeur.cn/problem/POJ-3040

/*
作为创纪录的牛奶产量的奖励，约翰决定每周给贝西一小笔零用钱。FJ拥有一组N（1 <= N <= 20）种不同面额的硬币，
其中每个面额的硬币均可整除较大面额的硬币（例如，1分硬币、5分硬币、10分硬币和50分硬币）。
使用给定的硬币面额，他想每周至少支付给贝西一定金额C（1 <= C <= 100,000,000）。
请帮助他计算他最多可以支付贝西多少周。

输入

第1行：两个以空格分隔的整数：N和C
第2行到第N+1行：每行对应一个硬币面额，并包含两个整数：
硬币面额V（1 <= V <= 100,000,000）和约翰手中该面额的硬币数量B（1 <= B <= 1,000,000）。
输出

第1行：一个整数，表示约翰可以支付贝西至少C零用钱的周数。

3 6
10 1
1 100
5 120

111

3 6
10 3
20 4
40 5

12

3 51
100 1
50 4
1 2

4


3 51
1 2
50 4
100 1

4

20 100000000
67108864 1000000
33554432 1000000
16777216 1000000
8388608 1000000
4194304 1000000
2097152 1000000
1048576 1000000
524288 1000000
262144 1000000
131072 1000000
65536 1000000
32768 1000000
16384 1000000
8192 1000000
4096 1000000
2048 1000000
1024 1000000
512 1000000
256 1000000
128 1000000

1340054


输入详情：
FJ每周想支付给贝西6美分。他手上有100个1美分硬币，120个5美分硬币和1个10美分硬币。

输出详情：
FJ可以用一个10美分硬币多支付给贝西1周，然后用两个5美分硬币支付给贝西10周，
最后用一个1美分硬币和一个5美分硬币支付给贝西100周。
*/

解答
直觉分析如下：
因为可选择的美分硬币数值是可整除的。所以我们需要尽量选择面额更大的硬币.
1 因为面值小的硬币总能替代面额大的硬币，更优。所以我们选择次优的较大面额的硬币，将更优的选择留给后面。
2 同样的凑齐刚好等于每周报酬的面值能留下更多的硬币数值给后面的选择,所以优先选择刚好等于每周报酬的组合，
然后再选择最接近、大于等于每周报酬的组合。
代码如下

#include <iostream>
#include <cstring>
#include <map>

using namespace std;

int n, c;
int ans;
map<int, int> mm;
map<int, int> usedmm;
int limit;

void GetusedArr() {
	//计算每次选择硬币的组合  逆序从大到小选择， 优先选择大额的 最接近等于每周报酬的组合
	for (map<int, int>::reverse_iterator it = mm.rbegin(); it != mm.rend(); it++) {
		if (it->second != 0 && limit >0  && limit >= it->first) {
			int used = min(limit / it->first, it->second);
			limit -= used * it->first;
			usedmm[it->first] += used;
		}
        //剩余值为0  则说明抽出了刚好等于每周报酬的组合
		if (limit == 0) break;
	}

	//贪心完所有金币 还没超出需要的金额. 说明凑不出刚好等于报酬的组合
    // 从小到大选择硬币，使用较小的面值进行填充 最接近等于每周报酬
	if (limit > 0) {
		for (map<int, int>::iterator it = mm.begin(); it != mm.end(); it++) {
			if (it->second > 0 && limit > 0 && mm[it->first] > usedmm[it->first]) {
				int used = 1;  int v = it->first; int cnt = it->second;
				limit -= v;
				usedmm[v] += 1;
			}
		}
	}

	return;
}

void solve() {

	while (1) {
		usedmm.clear();
		limit = c;
		GetusedArr();
        //limit 还不等于小于0  那么说明现在的硬币已经不能凑齐一周报酬了
		if (limit > 0) {
			cout << ans << endl; return;
		}
		//按照usedmm  查看能取几次
		int minget = 1000010;
		for (map<int, int>::iterator it = usedmm.begin(); it != usedmm.end(); it++) {
			int v = it->first;
			minget = min(minget, mm[v]/it->second);
		}
	
		ans += minget;

		//从已有的硬币里减去
		for (map<int, int>::iterator it = usedmm.begin(); it != usedmm.end(); it++) {
			int v = it->first;
			mm[v] -= minget * it->second;
		}
	}
}

int main()
{
	cin >> n >> c;

	for (int i = 0; i < n; i++) {
		int v, b; cin >> v >> b;
		if (v >= c) {
			ans += b;
		}
		else {
			mm[v] += b;
		}
	}

	solve();


	return 0;
}

我的视频题解空间