贪心专题
A
题目大意
给出 个木棍，每根木棍有长度 重量 ，当这两个特性都大于等于前一根木棍时，对当前木棍操作不需要时间，否则需要一分钟，特别地，第一根需要一分钟。
题解
定义结构体后，按照其中一个特性为第一关键字，另一特性为第二关键字从小到大排序，操作当前木棍后标记已经操作，同时检查它之后的木棍是否需要操作时间，若不用直接标记已操作。
贪心证明
若一个大的放在一个小的前面，则操作完大的之后小的操作时间一定无法忽略不计，总耗时大于等于从小到大排序的情形。
其他
我在写这题的时候误以为所有的 指的都是当前木棍堆的第一根木棍，对于这种题意依然可以使用贪心，具体解法见 这里 （类似）
B
题目大意
有 个人，每人有 张牌，牌的数字从 到 ，给出玩家拥有的所有牌号，每局游戏都是每人各出一张牌，数字最大的获胜记为当前局的赢家，求至少能赢的局数的最大值。
题解
为了使能赢的局数最大化，玩家不能浪费每张能够赢的牌，我们这样定义能够赢的牌：假设所有玩家出牌顺序从大到小，当前其他玩家的牌都小于等于这张牌牌号。
代码
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
| #include <bits/stdc++.h>
using namespace std;
bool f[1100];
int main() {
int m, n;
int cs = 1;
while (scanf("%d %d", &m, &n)) {
if (n == 0 && m == 0)
break;
memset(f, false, sizeof f);
for (int i = 1, a; i <= n; ++i) {
scanf("%d", &a);
f[a] = true;
}
int sum = 0;
int ans = 0;
for (int i = n * m; i >= 1; --i) {
if (sum <= 0 && f[i]) {
++ans;
} else if (sum > 0 && f[i]) {
--sum;
} else {
++sum;
}
}
printf("Case %d: %d\n", cs, ans);
++cs;
}
}
|
证明
若玩家出的一张牌牌号小于下一张，若这局能赢，下一局也一定能赢，（或者都不能赢），答案不变；若原本两局都能赢，现在这一局不能赢，下一局能赢，则答案少一。故这样得到的答案一定小于等于题解得到的答案。
其他
我他喵为什么会干出 的傻事
C
题解
- 对 从小到大排序，如果 相同，则按扣分从大到小排序。
- 如果当前作业扣分多，就用前面做扣分少的作业的时间来做这门作业；如果前面没有扣分较少的，就扣这门作业的分。（就是一个比较的过程）
证明
- 保证了处理顺序的合理性
- 保证了总扣分数值的最小化
D
题解
就，最大化不重叠的子区间个数
按结束时间从小到大排序
E
题解
显然平均值从大到小
F
题解
和 类似
只需让同时进行的操作尽可能多，就能让总时间尽可能少
有个处理细节，只要 （向下取整），两个就能同时操作
G
题解
总的思路：塞大的时候尽可能多地塞小的，从大到小处理
代码
（其实我写的好复杂 qwq）
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
| #include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
int main() {
int a1, a2, a3, a4, a5, a6;
scanf("%d %d %d %d %d %d", &a1, &a2, &a3, &a4, &a5, &a6);
while (a1 + a2 + a3 + a4 + a5 + a6 != 0) {
int ans = a6;
ans += a5;
a1 -= a5 * 11;
a1 = max(a1, 0);
ans += a4;
a2 -= a4 * 5;
if (a2 < 0) {
a1 += a2 * 4;
a1 = max(a1, 0);
}
a2 = max(a2, 0);
int tmp = a3 % 4;
ans += a3 / 4;
if (tmp == 1) {
++ans;
a2 -= 5;
if (a2 < 0) {
a1 += a2 * 4;
}
a1 -= 7;
}
if (tmp == 2) {
++ans;
a2 -= 3;
if (a2 < 0) {
a1 += a2 * 4;
}
a1 -= 6;
}
if (tmp == 3) {
++ans;
a2 -= 1;
if (a2 < 0) {
a1 += a2 * 4;
}
a1 -= 5;
}
a1 = max(a1, 0);
a2 = max(a2, 0);
tmp = a2 % 9;
ans += a2 / 9;
if (tmp > 0) {
++ans;
a1 -= 36 - tmp * 4;
}
a1 = max(a1, 0);
ans += a1 / 36;
if (a1 % 36)
++ans;
printf("%d\n", ans);
scanf("%d %d %d %d %d %d", &a1, &a2, &a3, &a4, &a5, &a6);
}
}
|
H
题目大意
在坐标轴上有 头牛，分别向其他牛 。给出牛的位置，求任意两位置的差的总和。
题解
这题考排序，不排序会超时
另外，由对称性，无需累加两次， 即可
I
题目大意
给 个商品的价格和卖出的截止时间，卖一个商品占一个单位时间，求最多能买多少钱
题解
按照截止时间从小到大排序，接着遍历时间，在每一个时间戳上，把所有截止时间小于等于当前时间的商品选择最大价值的进行售卖
可以用一个截止时间从小到大的优先队列实现，涉及重载运算符
J
题解
从坐标轴找小岛显然很麻烦，因为是二维的。所以直接降维，逆向思维，从小岛找到对应的坐标轴范围，就成了一个一维的最小区间点覆盖问题。
K
题解
对坑按起始位置从小到大排序，在循环中计算每一段需要木板的数量，当长度不等于木板长度倍数时，数量 ，并更新木板覆盖末位置，与下一段的初位置进行比较，若大于下一段的初位置，则更新初位置。
L
题解
假设从 走到 ，则路上总共耗时 ，在这个时间段里，任一时刻只要选择当前 ~ 能钓到最多鱼的湖即可（因为能瞬移），相同则选择序号小的。
M
题解
乍一看以为是树形 （因为我菜），思考了一下发现直接用并查集的思想就能贪心。
首先，很容易想到，尽早访问权值较大的点能使代价尽可能小。但是必须得访问他的父亲节点后才能访问它，所以就存在一定的顺序问题。
因为从树根往下顺序很难确定，所以考虑从叶子节点往上归并。
在这个过程中，为了确定每个节点的子节点合并到它身上的顺序，我们可以引入一个新定义的权值：平均权值（即：真实权值的和 合并的节点数），相当于这个节点由多个相等权值的节点组成，以此来作为比较权值大小的依据。
在得到平均权值之后，按照平均权值从大到小的顺序合并上去，不断归并不断更新答案，直到所有节点都合并到了 ，即可得到最终答案。