【GESP】C++五级/四级练习题 luogu-P1413 坚果保龄球
GESP C++ 五级/四级练习题，贪心思想思想考点，四级考生也可以练习，因为难度不大。题目难度⭐⭐★☆☆，适合五级入门和四级练习，洛谷难度等级普及-。
luogu-P1413 坚果保龄球
题目要求
题目描述
PVZ 这款游戏中，有一种坚果保龄球。zombie 从地图右侧不断出现，向左走，玩家需要从左侧滚动坚果来碾死他们。
我们可以认为地图是一个行数为 $6$，列数为 $60$ 的棋盘。zombie 出现的那一秒站在这一行的第 $60$ 列，之后每秒向左移动一步。玩家可以随时在屏幕最某一行第一列摆放坚果，这一行的 zombie 瞬间全被滚过去的坚果碾死。如果 zombie 走到第 $1$ 列没有被消灭，如果再向左走，则你的大脑就会被 zombie 吃掉。
现在有 $n$ 只 zombie！告诉你每只 zombie 出现的时间以及在出现的行数（可能会同时出现同一位置的僵尸），请问至少需要多少坚果才能消灭所有的 zombie。
输入格式
第一行一个正整数 $n$，表示 zombie 数量。
之后 $n$ 行中，每行两个正整数 $P$ 和 $t$，分别表示 zombie 所在行和 zombie 出现的时间。
输出格式
一个正整数，最少需要的坚果数。
输入输出样例 #1
输入 #1
1
2
3
4
5
6
7
8
9
10
11
10
1 1
1 61
2 1
2 60
3 1
3 2
3 3
3 4
4 1
4 99999
输出 #1
1
6
说明/提示
数据范围及约定
对于全部数据，$n \le 2000$，$t \le 100000$，$1 \le P \le 6$。
题目分析
1. 理解题意
- 地图规格：6 行 60 列。
- 僵尸移动：僵尸在第 $t$ 秒出现在第 60 列，每秒向左移动一步。它到达第 1 列的时间是 $t + 59$ 秒。如果第 $t + 60$ 秒它还没被消灭，玩家就输了。
- 坚果作用：在某一行放置坚果，该行当前在地图上的所有僵尸都会被瞬间消灭。
- 核心逻辑：一个在 $t$ 秒出现的僵尸，其在地图上的存活时间区间为 $[t, t+59]$。如果我们想用一个坚果消灭它，必须在 $S \in [t, t+59]$ 这个时间点放置坚果。
2. 贪心策略
为了使总坚果数最少，我们要让每一个坚果的“收益”最大化，即一个坚果尽可能覆盖更多的僵尸。
- 分行独立：由于坚果只能消灭同一行的僵尸，且行数只有 6 行，我们可以对每一行独立处理。
- 时间排序：对于每一行，将僵尸出现的时间从小到大排序。
- 区间覆盖：假设这一行最早出现的僵尸时间是 $t_1$，那么为了消灭它，我们最晚可以在 $t_1 + 59$ 秒放置一个坚果。这个坚果不仅能消灭 $t_1$，还能消灭所有在 $[t_1, t_1+59]$ 之间出现的僵尸。
- 后续处理：跳过被第一个坚果覆盖的所有僵尸，找到下一个未被消灭的僵尸，重复上述贪心过程。
3. 复杂度分析
- 时间复杂度：主要耗时在排序。如果有 $n$ 个僵尸，总的排序复杂度为 $O(n \log n)$。遍历过程是 $O(n)$。对于 $n \le 2000$ 的数据规模，此算法非常高效。
- 空间复杂度：需要存储所有僵尸的信息，空间复杂度为 $O(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
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
#include <algorithm>
#include <iostream>
#include <vector>
// 题目：P1413 坚果保龄球
// 链接：https://www.luogu.com.cn/problem/P1413
// 核心思路：
// 使用贪心算法。对于每一行，我们将僵尸出现的时间进行排序。
// 首先放置一个坚果消灭第一个僵尸，这个坚果可以覆盖一定的时间范围（60秒内）。
// 如果下一个僵尸出现的时间完全在这个范围内，就不需要新的坚果。
// 否则，就需要放置一个新的坚果。
int main() {
int n;
// 读取僵尸的总数量
std::cin >> n;
// 创建一个大小为7的二维向量，实际上只使用索引 1 到 6，对应 6 行
std::vector<std::vector<int>> v(7);
// 读取每个僵尸的信息
for (int i = 0; i < n; i++) {
int row, time;
std::cin >> row >> time;
// 将僵尸出现的时间记录在对应的行中
v[row].push_back(time);
}
// 对每一行僵尸出现的时间进行升序排序
for (int i = 1; i <= 6; i++) {
std::sort(v[i].begin(), v[i].end());
}
int count = 0; // 记录总共需要的坚果数量
// 遍历每一行
for (int i = 1; i <= 6; i++) {
std::vector<int> row = v[i];
// 如果这一行有僵尸
if (row.size() > 0) {
count++; // 首先需要一个坚果来对付这一行的第一个僵尸
int last_time = row[0]; // 记录上一次放置坚果的时间
// 遍历这一行的其余僵尸
for (int j = 1; j < row.size(); j++) {
// 如果当前僵尸出现的时间与上一个坚果的时间差超过 59 秒
// 说明上一个坚果已经失效（跑出地图），需要一个新的坚果
// 地图宽度为60，坚果和僵尸相对运动或覆盖逻辑一般理解为一个坚果管辖
// 60 秒的区间
if (row[j] - last_time > 59) {
count++;
last_time = row[j]; // 更新最新放置坚果的时间
}
}
}
}
// 输出最少需要的坚果数
std::cout << count << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
