流浪地球

题目描述

流浪地球计划在赤道上均匀部署了N个转向发动机，按位置顺序编号为0~N。

​ 1). 初始状态下所有的发动机都是未启动状态;

​ 2). 发动机启动的方式分为”手动启动”和”关联启动”两种方式;

​ 3). 如果在时刻1一个发动机被启动，下一个时刻2与之相邻的两个发动机就会被"关联启动”;

​ 4). 如果准备启动某个发动机时，它已经被启动了，则什么都不用做;

​ 5). 发动机0与发动机N-1是相邻的;

地球联合政府准备挑选某些发动机在某些时刻进行"手动启动”。当然最终所有的发动机都会被启动。 哪些发动机最晚被启动呢?

输入描述

第一行两个数字N和E，中间有空格N代表部署发动机的总个数，E代表计划手动启动的发动机总个数 1<N<=1000. 1<=E<= 1000. E<=N

接下来共E行，每行都是两个数字T和P，中间有空格T代表发动机的手动启动时刻，P代表此发动机的位置编号。0 <= T <= N 0 <= P < N

输出描述

第一行一个数字N，以回车结束N代表最后被启动的发动机个数

第二行N个数字，中间有空格，以回车结束每个数字代表发动机的位置编号，从小到大排序

示例1

输入：
8 2
0 2
0 6

输出：
2
0 4

说明：
8个发动机;
时刻0启动(2,6);
时刻1启动(1,3,5,7)(其中1,3被2关联启动，5，7被6关联启动)
时刻2启动(0,4)(其中0被1,7关联启动，4被3,5关联启动);
至此所有发动机都被启动，最后被启动的有2个，分别是0和4。

C++

#include <bits/stdc++.h>

using namespace std;

int main() {
    // N代表部署发动机的总个数，E代表计划手动启动的发动机总个数
    int n, e;
    cin >> n >> e;

    // 使用 pair<int, int> 类型存放<启动时刻，发动机位置编号>
    typedef pair<int, int> pii;

    // 使用优先队列根据时间顺序来排序待启动的发动机
    priority_queue<pii, vector<pii>, greater<>> q;

    // 输入所有手动启动事件
    for (int i = 0, t, p; i < e; i++) {
        cin >> t >> p;
        q.emplace(t, p);  // 将(启动时刻, 发动机位置)加入优先队列
    }

    // 已经启动的发动机集合，用于避免重复启动
    unordered_set<int> started;

    // 记录最后一批启动的发动机
    vector<int> last;

    // BFS 执行，处理每个时刻的启动事件
    while (!q.empty()) {
        last.clear();  // 清空上一轮启动的发动机

        // 获取当前时刻启动的所有发动机
        int time = q.top().first;  // 当前时刻
        while (!q.empty() && q.top().first == time) {
            auto [t, p] = q.top();  // 获取启动时刻和发动机位置
            q.pop();

            // 如果该发动机已经启动，跳过
            if (started.count(p)) {
                continue;
            } else {
                // 启动该发动机
                started.insert(p);
                last.push_back(p);

                // 启动该发动机后，需要启动它的相邻发动机（循环队列）
                int lp = (p - 1 + n) % n;  // 左邻居
                int rp = (p + 1) % n;      // 右邻居

                // 如果左邻居没有启动，安排它在下一个时刻启动
                if (!started.count(lp)) q.emplace(time + 1, lp);

                // 如果右邻居没有启动，安排它在下一个时刻启动
                if (!started.count(rp)) q.emplace(time + 1, rp);
            }
        }
    }

    // 最后启动的发动机从小到大排序
    sort(last.begin(), last.end());

    // 输出最后被启动的发动机的数量和编号
    int size = last.size();
    cout << size << endl;
    for (int i = 0; i < size; i++) {
        if (i + 1 == size) cout << last[i] << endl;
        else cout << last[i] << " ";
    }

    return 0;
}

题解

1. 题目类型

这个题目属于 广度优先搜索（BFS） 类型的算法题。

2. 解题思路

• 我们有 N 个发动机，并且每个发动机都有一个启动时刻。启动时，发动机会触发相邻发动机的“关联启动”。因此，我们的任务是模拟发动机的启动过程，找到所有发动机启动的最后时刻，并且输出最后被启动的发动机。
• 广度优先搜索（BFS） 适合这种“依赖于邻居”或“逐步传播”类型的场景。在这题中，如果某个发动机被启动，它会在下一个时刻启动它的相邻发动机，类似于图中的遍历问题。

3. 代码大致描述

1. 输入解析：首先，读取 N 和 E，分别代表发动机的总数和手动启动的发动机数量。接着读取每一个手动启动事件，包括启动的时刻和发动机的位置。
2. 优先队列：为了保证每次最早启动的发动机被处理，我们使用了一个 优先队列（min-heap）。队列中的元素是一个 (启动时刻, 发动机位置) 的二元组，通过时刻从小到大的顺序处理启动。
3. BFS 执行：
   • 对于每一个时刻，遍历所有该时刻启动的发动机。
   • 如果该发动机尚未启动，则将其启动，并且安排它的相邻发动机在下一个时刻启动。
   • 使用 unordered_set 来记录已启动的发动机，避免重复启动。
4. 输出最后被启动的发动机：在 BFS 完成后，所有发动机都已启动。最后启动的发动机是那些在最晚的时刻启动的发动机。

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏