poj 3040 Allowance 贪心

缘起

日常浪费生命 poj 3040 Allowance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
作为创纪录的牛奶生产的奖励，农场主约翰决定开始给Bessie奶牛一个小的每周津贴。FJ有一套硬币N种
（1≤N≤20）不同的面额，每枚硬币是所有比他小的硬币面值的倍数，例如1美分硬币、5美分硬币、10美分硬币和50
美分硬币。使用这些硬币，FJ每周至少给Bessie C（1 <= C <=100000000）美分。请你计算他最多能给Bessie
几周

【输入】
第一行是N和C（1 <= N <= 20，1 <= C <= 100,000,000）， 后面N行每行是两个整数，前者是面额（V），后者是面额的张数（B），1 <= V <= 100,000,000，1 <= B <= 1,000,000

【输出】
最多能发几周工资?

【样例输入】
3 6
10 1
1 100
5 120

【样例输出】
111

【限制】
1s

【提示】
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的面额有多少张就支出多少周——毕竟不可分割. 而<C的面额因为不够，所以要拼凑. 怎么拼凑呢? 首先从大到小进行拼凑直至<=C. 然后从小到大拼凑直至>=C. 举个例子

1
2
3
4
5
6
5 54
2 8
4 4
8 10
16 3
32 9

则首先32+16+4+2 （从大到小拼凑）, 然后因为已经拼凑够了，所以不需要再从小到大拼凑直至>=C了.

前三轮都是这样. 即

1
2
3
32 16 4 2
32 16 4 2
32 16 4 2

余下32的6张，8的10张，4的一张，2的5张.

然后

1
32+8*2+4+2

余下

32的5张，8 的8张，2的4张, 然后 

1
32+8*2+2*3

余下 32的4张，8的6张，2的1张, 然后

1
2
3
32+8*2+2
+
8

其中第一行的是从大到小，第三行的是从小到大. 余下 32的3张，8的三张，然后

1
2
3
32+8*2
+
8

其中第一行是从大到小，第三行是从小到大. 余下 32的2张，8的

1
32+32

所以最长可以支付8天的薪资.

根据上述贪心思想，可以给出如下代码，但是可惜，被T掉了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL
typedef long long LL; // v*b 可能达到 10^14

LL n,c;

struct M 
{
	LL v,b;
	bool operator <(M m)
	{
		return v<m.v;
	}
}money[25];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int ans = 0, m=0;
	scanf("%lld%lld", &n, &c);
	for (int i = 0; i<n;i++)
	{
		scanf("%lld%lld", &money[i].v, &money[i].b);
		if (money[i].v<c) m++;
		else ans+=money[i].b; // >=c 的面额因为不可分割, 所以直接加即可
	}
	sort(money, money+n); // 只用考虑money[0,...,m-1]即可
	while (1)
	{
		int t = c; // 要凑够t元
		for (int i = m-1,x; ~i; i--) // 首先从大到小考虑面额
		{
			if (money[i].b)
			{
				x = min(t/money[i].v, money[i].b); // money[i]需要奉献x张
				money[i].b-=x;
				t-=x*money[i].v;
			}
			if (t<=0) break;
		}
		if (t<=0) // 如果已经凑够了
		{
			ans++;
			continue;
		}
		for (int i = 0,x; i<m ;i++) // 再从小到大考虑面额
		{
			if (money[i].b)
			{
				x = min(money[i].b, t%money[i].v?(t/money[i].v+1):t/money[i].v); // money[i]面额需要奉献x张
				money[i].b-=x;
				t-=x*money[i].v;
			}
			if (t<=0) break;
		}
		if (t<=0) ans++; // 此轮凑够了
		else break; // 已经无法凑够了
	}
	printf("%d\n", ans);
	return 0;
}

怎么优化呢? 或者说上述浪费时间的点在哪里? 在模拟 ! 也就是其实某次求出了一种方案之后，其实下一次很可能依旧是这种方案（就像是上面的例子中开头的三个 32 16 4 2 一样），而不需要再次求了，如果模拟的话，会超时的. 那什么时候求呢? 就在一种面额数量归零的时候就要求了. 这样做的话，可以加速贪心的过程.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
typedef long long LL; // v*b 可能达到 10^14

LL n,c;
int need[25]; // 缓存支付方案

struct M 
{
	LL v,b;
	bool operator <(M m)
	{
		return v<m.v;
	}
}money[25];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int ans = 0, m=0;
	scanf("%lld%lld", &n, &c);
	for (int i = 0; i<n;i++)
	{
		scanf("%lld%lld", &money[i].v, &money[i].b);
		if (money[i].v<c) m++;
		else ans+=money[i].b; // >=c 的面额因为不可分割, 所以直接加即可
	}
	sort(money, money+n); // 只用考虑money[0,...,m-1]即可
	bool flag = true; // 支付方案是否需要重新求
	while (1)
	{
		int t = c; // 要凑够t元
		if (flag) // 重新求支付方案
		{
			memset(need, 0, sizeof(need)); // 重置支付方案
			for (int i = m-1,x; ~i; i--) // 首先从大到小考虑面额
			{
				x = min(t/money[i].v, money[i].b); // money[i]需要奉献x张
				money[i].b-=x;
				t-=x*money[i].v;
				need[i] = x; // 面额i需要支付x张
			}
			if (t<=0) // 如果已经凑够了
			{
				ans++;
				// 至此, 求出了一种薪资支付方案need, 下面要检查下一次是否可用.
				flag = false; // 默认可用
				for (int i = 0; i<m;i++)
				{
					if (money[i].b<need[i])
					{
						flag = true; // 发现下次就不可用了,还是要重新求
						break;
					}
				}
				continue;
			}
			for (int i = 0,x; i<m ;i++) // 再从小到大考虑面额
			{
				x = min(money[i].b, t%money[i].v?(t/money[i].v+1):t/money[i].v); // i需要奉献x张
				money[i].b-=x;
				t-=x*money[i].v;
				need[i]+=x;
				if (t<=0) break;
			}
			// 至此, 求出了一种薪资支付方案need, 下面要检查下一次是否可用.
			flag = false; // 默认可用
			for (int i = 0; i<m;i++)
			{
				if (money[i].b<need[i])
				{
					flag = true; // 发现下次就不可用了,还是要重新求
					break;
				}
			}
		}
		else // 直接使用缓存的薪资支付方案——这是加速贪心的关键
		{
			t = 0; // 直接归零
			for (int i = 0; i<m;i++)
			{
				money[i].b-=need[i];
				if (money[i].b<need[i]) // 如果下一次不够用了
				{
					flag = true; // 则下次要重新求支付方案
				}
			}
		}
		if (t<=0) ans++; // 此轮凑够了
		else break; // 已经无法凑够了
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

Status Accepted
Time 188ms
Memory 88kB
Length 1927
Lang C++
Submitted 2019-08-25 22:28:29
Shared
RemoteRunId 20800810