C++贪心算法详解：洛谷P1413坚果保龄球题解与GESP考级练习

题目要求

题目描述

PVZ 这款游戏中，有一种坚果保龄球。zombie 从地图右侧不断出现，向左走，玩家需要从左侧滚动坚果来碾死他们。

我们可以认为地图是一个行数为，列数为的棋盘。zombie 出现的那一秒站在这一行的第列，之后每秒向左移动一步。玩家可以随时在屏幕最某一行第一列摆放坚果，这一行的 zombie 瞬间全被滚过去的坚果碾死。如果 zombie 走到第列没有被消灭，如果再向左走，则你的大脑就会被 zombie 吃掉。

现在有只 zombie！告诉你每只 zombie 出现的时间以及在出现的行数（可能会同时出现同一位置的僵尸），请问至少需要多少坚果才能消灭所有的 zombie。

输入格式

第一行一个正整数，表示 zombie 数量。

之后行中，每行两个正整数和，分别表示 zombie 所在行和 zombie 出现的时间。

输出格式

一个正整数，最少需要的坚果数。

输入输出样例 #1

输入 #1

10
1 1
1 61
2 1
2 60
3 1
3 2
3 3
3 4
4 1
4 99999

输出 #1

6

说明/提示

数据范围及约定

对于全部数据，，，。

题目分析

1. 理解题意

• 地图规格：6 行 60 列。
• 僵尸移动：僵尸在第 秒出现在第 60 列，每秒向左移动一步。它到达第 1 列的时间是 秒。如果第 秒它还没被消灭，玩家就输了。
• 坚果作用：在某一行放置坚果，该行当前在地图上的所有僵尸都会被瞬间消灭。
• 核心逻辑：一个在 秒出现的僵尸，其在地图上的存活时间区间为 。如果我们想用一个坚果消灭它，必须在 这个时间点放置坚果。

2. 贪心策略

为了使总坚果数最少，我们要让每一个坚果的“收益”最大化，即一个坚果尽可能覆盖更多的僵尸。

• 分行独立：由于坚果只能消灭同一行的僵尸，且行数只有 6 行，我们可以对每一行独立处理。
• 时间排序：对于每一行，将僵尸出现的时间从小到大排序。排序是算法学习的基础操作。
• 区间覆盖：假设这一行最早出现的僵尸时间是 ，那么为了消灭它，我们最晚可以在 秒放置一个坚果。这个坚果不仅能消灭 ，还能消灭所有在 之间出现的僵尸。
• 后续处理：跳过被第一个坚果覆盖的所有僵尸，找到下一个未被消灭的僵尸，重复上述贪心过程。

掌握贪心等算法思想对于解决此类最优化问题至关重要。

3. 复杂度分析

• 时间复杂度：主要耗时在排序。如果有 个僵尸，总的排序复杂度为 。遍历过程是 。对于 的数据规模，此算法非常高效。
• 空间复杂度：需要存储所有僵尸的信息，空间复杂度为 。

示例代码

#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;
}