2019十一集训贪心专题选讲

发表于 | 更新于 | 分类于 | 评论数：
讲题人是THU的王之栋，相当的神仙.

New Year Snowmen

要堆起一个雪人，需要三个不同大小的雪球。

现在有$n$个给定大小的雪球，问最多能堆起多少个雪人，并输出方案。($n \leq 10 ^ 5$)

Codeforces 140C

好像这个结论比较难证，但是很容易想出来。就是说我们每次取出目前数量最多的雪球种类，这样能取出来的雪人的个数一定是最多的。至于证明，还是留给读者慢慢想吧。。。

因此做法很一目了然了，基本上就是记录每一种雪球的种类数，然后用优先队列维护一下就可以了，虽然做法很简单，但是有一些细节仍然需要注意，建议大家尝试动手写一写。

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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std ;
typedef long long LL ;
const int MAXN = 100010 ;
const int MAXM = 100010 ;
const int INF = 0x7fffffff ;
int N, Tot = 1, Ans ;
struct Node {
	int R, ID ;
	bool operator < (Node B) const {
		return R < B.R ;
	}
}	E[MAXN] ;
struct Node2 {
	int X[4] ;
}	G[MAXN] ;

inline int Read() {
	int X = 0, F = 1 ; char ch = getchar() ;
	while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
	while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
	return X * F ;
}
priority_queue<Node> Q ;

int main() {
	N = Read() ; 
	for (int i = 1 ; i <= N ; i ++)
		E[i].R = Read(), E[i].ID = i ;
	sort(E + 1, E + N + 1) ;
	E[0].R = - INF ;
	for (int i = 2 ; i <= N + 1 ; i ++) {
		if (E[i].R != E[i - 1].R) {
			Node Now ;
			Now.ID = E[i - 1].R, Now.R = Tot ;
			Q.push(Now) ; Tot = 1 ;
		}	else Tot ++ ;
	}
	Node NOW ; NOW = Q.top() ; int Cnt = 0 ;

	while (Q.size() >= 3) {
		Node Now[4] ;
		for (int i = 1 ; i <= 3 ; i ++) {
			Now[i] = Q.top() ; Q.pop() ;
			Now[i].R -- ;
		}
		for (int i = 1 ; i <= 3 ; i ++)
			if (Now[i].R) Q.push(Now[i]), Cnt ++ ;
		Ans ++ ;
		for (int i = 1 ; i <= 3 ; i ++)
			G[Ans].X[i] = Now[i].ID ;
	}
	printf("%d\n", Ans) ;
	for (int i = 1 ; i <= Ans ; i ++) {
		int L = min(G[i].X[1], min(G[i].X[2], G[i].X[3])),
		    R = max(G[i].X[1], max(G[i].X[2], G[i].X[3])) ;
		printf("%d ", R) ;
		for (int j = 1 ; j <= 3 ; j ++)
			if (G[i].X[j] < R && G[i].X[j] > L) printf("%d ", G[i].X[j]) ;
		printf("%d\n", L) ;
	}
	return 0 ;
}

Discounts

超市打折，如果购物车里有至少一个凳子，则可半价购买购物车里最便宜的一个物品。

现在你要购买$n$个物品，其中一些是凳子。你有$K$个购物车，求一个最优的购买方案，使得花费的价格最少。

$k \leq n \leq 10 ^ 5$

Codeforces 161B

贪心策略：对于所有的凳子，最好的情况是独占一个购物车。因此最好的决断是对于所有的凳子，使其尽量独占一个购物车，如果不能使所有的凳子独占一个购物车（K - 1 < 凳子数），则将所有的凳子按降序排序之后从前往后填充，然后将剩下的凳子和非凳子的物品都放到最后一个购物车当中。

策略非常简单，但是写起来很麻烦，需要分类讨论$K - 1$和凳子数的关系，很是烦人，建议大家写一写，很能锻炼码力的。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std ;
typedef long long LL ;
const int MAXN = 1010 ;
const int MAXM = 1010 ;
const int INF = 0x7fffffff ;
int N, K, C_T, O_T ;
double Ans ;
struct NODE {
	int C, T, ID ;
}	E[MAXN], Chair[MAXN], Othe[MAXN] ;

inline int Read() {
	int X = 0, F = 1 ; char ch = getchar() ;
	while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
	while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
	return X * F ;
}

inline bool CMP(NODE A, NODE B) {
	return A.C > B.C ;
}

int main() {
	N = Read() ; K = Read() ;
	for (int i = 1 ; i <= N ; i ++)
		E[i].C = Read(), E[i].T = Read(), E[i].ID = i ;
	for (int i = 1 ; i <= N ; i ++)
		if (E[i].T == 1) Chair[++ C_T] = E[i] ;
	for (int i = 1 ; i <= N ; i ++)
		if (E[i].T == 2) Othe[++ O_T] = E[i] ;
	sort(Chair + 1, Chair + C_T + 1, CMP) ;
	if (C_T > K - 1) {
		for (int i = 1 ; i <= K - 1 ; i ++)
			Ans += (double) Chair[i].C / 2 ;
		int Min = INF ;
		for (int i = 1 ; i <= O_T ; i ++)
			Ans += Othe[i].C, Min = min(Min, Othe[i].C) ;
		for (int i = K ; i <= C_T ; i ++)
			Ans += Chair[i].C, Min = min(Min, Chair[i].C) ;
		Ans -= (double) Min / 2 ;

	}
	if (C_T <= K - 1) {
		for (int i = 1 ; i <= C_T ; i ++)
			Ans += (double) Chair[i].C / 2 ;
		for (int i = 1 ; i <= O_T ; i ++)
			Ans += Othe[i].C ;
	}
	printf("%.1lf\n", Ans) ;
	if (C_T >= K - 1) {
		for (int i = 1 ; i <= K - 1 ; i ++)
			cout << "1 " << Chair[i].ID << endl ;
		cout << O_T + C_T - K + 1 << " " ;
		for (int i = K ; i <= C_T ; i ++)
			cout << Chair[i].ID << " " ;
		for (int i = 1 ; i <= O_T ; i ++)
			cout << Othe[i].ID << " " ;
		cout << endl ;
	}
	if (C_T < K - 1) {
		for (int i = 1 ; i <= C_T ; i ++)
			cout << "1 " << Chair[i].ID << endl ;
		for (int i = 1 ; i <= K - C_T - 1 ; i ++)
			cout << "1 " << Othe[i].ID << endl ;
		cout << O_T - K + C_T + 1 << " " ;
		for (int i = K - C_T ; i <= O_T ; i ++)
			cout << Othe[i].ID << " " ;
	}
	return 0 ;
}

叠罗汉

有$n$个罗汉，每个罗汉有重量$w$和力量$s$。

定义一个罗汉的危险值为他上面所有物品的重量之和减去他的力量。

安排一个顺序使得危险值最大的罗汉的危险值最小。

$n≤10^5$

首先，我们可以发现对于两个罗汉$i$和$j$，他们之间的上下顺序对于下方所造成的的贡献是完全无关的，因此我们可以将整个问题拆分成一个个两罗汉的小问题逐一解决。假设这两个罗汉上方的罗汉一共重量G。

那么考虑这两个罗汉，如果是$i$在上面的话，那么他们两个造成的危险值是：

如果是$j$在上面的话，造成的危险值是：

讨论这两种情况可以发现当$w_i + s_i$比较小的时候造成的危险值最大的罗汉危险值最小，于是$w_i + s_i$比较小的罗汉放到上面比较优。所以最优解就是按照$w_i +s_i$排一下序就可以了。

建筑抢修

基地里有 $N$ 个建筑设施受到了严重的损伤，但只有 一个修理工人。

修复一个建筑都需要 T1 的时间，工人一次只能修一个。如果某个建筑在T2时间之内没有修理完毕 ，这个建筑就报废了。

你的任务是制订一个合理的维修顺序，以抢修尽可能多的建筑。

JSOI2007

开始我是估摸着能找出来一个确定的枚举顺序，$sort$一下$O(N)$就处理完了。但是我把$T1$和$T2$反复折腾还是没有找出一个正确的顺序，因为我总是能够找出反例，一般这个时候这种类型的贪心就只有一种路可走了：按一定顺序先进行排序，然后在枚举过程中根据另一变量对当前枚举顺序做出修改。

这个地方一眼的枚举方式就是按照$T2$从小到大枚举，然后我们根据$T1$在此基础上对当前枚举顺序做一下调整。

假设当前使用了的总时间为$Tot$，如果$Tot + T1 <= T2$，那么我们直接维修当前i就可以。

而如果建筑i不能在$T1$时间内修复，我们转而在之前已经修理过的所有建筑中选出$T1$最大的j号点来，如果$T1_j > T2_i$那么我们更改决策，放弃$j$而修$i$。

这种决策为何是正确的就在于如果第$i$号建筑的出现时间不足，由于我们是按照$T2$进行排序，因此前面的节点最多修复了$i - 1$，那么我们就尽量选择$T1$总和较小的$i - 1$个建筑，给后面的决策留出更加充足的时间。因此，这个决策没有劣处。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std ;
typedef long long LL ;
const LL MAXN = 200010 ;
const LL MAXM = 200010 ;
const LL INF = 0x7fffffff ;
LL Tot, Ans ;
struct HOUSE {
	LL T1, T2 ;
	bool operator < (HOUSE B) const {
		return T2 < B.T2 ;
	}
}	E[MAXN] ;
priority_queue <long long> Q ;

inline LL Read() {
	LL X = 0, F = 1 ; char ch = getchar() ;
	while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
	while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
	return X * F ;
}
LL N = Read() ;

int main() {
	for (LL i = 1 ; i <= N ; i ++) 
		E[i].T1 = Read(), E[i].T2 = Read() ;
	sort(E + 1, E + N + 1) ;
	for (LL i = 1 ; i <= N ; i ++)
		if (E[i].T1 + Tot <= E[i].T2)
			Tot += E[i].T1, Q.push(E[i].T1), Ans ++ ;
		else if (Q.top() > E[i].T1 && Tot - Q.top() + E[i].T1 <= E[i].T2)
				Tot -= Q.top() - E[i].T1, Q.pop(), Q.push(E[i].T1) ;
	printf("%lld", Ans) ;
	return 0 ;
}

删数问题

给定一个高精度的大正整数S（S最长可达240位），你需要去掉其中任意N位数字。剩下的数字按原次序组成一个新的正整数S’。

对给定的NS，寻找一种方案使得剩下的数字组成的新数S’最小。

LuoguP1106

这个题的话，不管花多长时间，我感觉最后所有人应该还是都想得出来的。所以我在这里就直接下结论了。

我们都知道贪心是可以由局部最优解推出全局最优解的，于是我们只要保证每一步都是最优的，那么最终答案也是最优的，因此我们每一次都选择使当前数字序列最大的方式进行删数。从高位到低位遍历，如果各位数字递增，那么删除最后一个数字，否则删除第一个递减区间的第一个数字。重复N次就可以了。（实际上就是删除第一个极大值啦。。。

而如何简化一下程序呢？题目要求我们删数，我们不妨设为选数，按照上方的思想，我们可以每次直接选取整个序列中最小的并且位数最高的一个数，然后将他的左边部分全部删去，然后对于左边的序列我们再次进行同样的操作就可以保证结果最优。至于如何证明这个情况，我建议大家从“答案这个数列的各个位数”方面入手分析。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std ;
typedef long long LL ;
const LL MAXN = 300 ;
const LL INF = 0x7fffffff ;
string N ; int L, K, Data[MAXN], Last, Cnt, Min, T = 1, F ;

inline LL Read() {
	LL X = 0, F = 1 ; char ch = getchar() ;
	while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
	while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
	return X * F ;
}

int main() {
	cin >> N >> K ; L = N.length() ;
	for (int i = 1 ; i <= L ; i ++) Data[i] = N[i - 1] - '0' ;
	Last = L - K ;
	while (Cnt < Last) {
		Min = T ;
		for (int i = T ; i <= K + T ; i ++)
			if (Data[Min] > Data[i]) Min = i ;
		if (Data[Min]) F = 1 ;
		if (F) cout << Data[Min] ;
		K -= Min - T, T = Min + 1, Cnt ++ ;
	}
	if (! F) puts("0") ;
	return 0 ;
}

取数游戏

给出n个正整数，你需要把它们连接成一排，组成一个最大的多位整数。

例如：n=3时，3个整数13、312、343，连成的最大整数为34331213。

又如：n=4时，4个整数7、13、4、246，连成的最大整数为7424613。

$ n≤10^5$

没错这是一道很水的题。只需要从高位向低位判断就可以了。

个屁。这样说起来好像是很容易但是仔细想一想怎么写你就会发现自己陷入一个很智障的无底洞。

我们考虑重新定义字符串的大小关系，对于两个字符串A, B如果$A后面接B$比$B后面接A$大，那么我们才定义$A >B$，（12， 121）

然后我们对于所有的数都进行一次这样的比较，直接按照这样的法则sort就可以了。

兔子与樱花

HEOI2015

本文标题:2019十一集训贪心专题选讲

文章作者:Sue Shallow

发布时间:2019年10月02日 - 18:41:20

最后更新:2019年11月11日 - 19:52:27

原始链接:http://Yeasion.github.io/2019/10/02/2019十一集训贪心专题选讲/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。