刷题笔记合集🔗

流浪地球

问题描述

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

1. 初始状态下所有的发动机都是未启动状态；
2. 发动机起动的方式分为"手动启动"和"关联启动"两种方式；
3. 如果在时刻 一个发动机被启动，下一个时刻 与之相邻的两个发动机就会被"关联启动"；
4. 如果准备启动某个发动机时，它已经被启动了，则什么都不用做；
5. 发动机 与发动机 是相邻的。

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

输入格式

第一行包含两个整数 和 ，用空格分隔。

• 代表部署发动机的总个数
• 代表计划手动启动的发动机总个数
• ，，

接下来共 行，每行包含两个整数 和 ，用空格分隔。

• 代表发动机的手动启动时刻
• 代表此发动机的位置编号
• ，

输出格式

第一行输出一个整数 ，表示最后被启动的发动机个数。

第二行输出 个整数，表示最后被启动的发动机的位置编号，从小到大排序，用空格分隔。

样例输入 1

8 2
0 2
0 6

样例输出 1

2
0 4

样例解释 1

8 个发动机，时刻 0 启动 2 和 6 号发动机。

样例输入 2

8 2
0 0
1 7

样例输出 2

1
4

样例解释 2

8 个发动机，时刻 0 启动 0 号发动机，时刻 1 启动 7 号发动机。

数据范围

题解

这道题目可以通过模拟发动机启动过程来解决。

使用一个数组来记录每个发动机的启动时间，初始化为一个足够大的值表示未启动。然后按照输入的顺序模拟手动启动和关联启动的过程。

具体步骤如下：

1. 初始化一个长度为 的数组 start_time，所有元素设为一个较大的数字。
2. 对于每次手动启动，更新对应发动机的启动时间。
3. 模拟关联启动：从时刻 0 到 ，检查每个发动机，如果它在当前时刻启动，则更新其相邻两个发动机的启动时间（如果尚未启动）。
4. 遍历 start_time 数组，找出最大的启动时间，这就是最后启动的时间。
5. 再次遍历数组，统计并输出启动时间等于最大启动时间的发动机编号。

这种方法的时间复杂度为 ，空间复杂度为 。对于给定的数据范围，这个解法是足够的。

参考代码

以下是五种语言的实现，都包含了详细的注释：

• Python

def solve():
    # 读取输入
    N, E = map(int, input().split())
    
    # 初始化启动时间数组，初始值设为 N+1 表示未启动
    start_time = [10 * N+1] * N
    
    # 处理手动启动的输入
    for _ in range(E):
        T, P = map(int, input().split())
        start_time[P] = min(start_time[P], T)  # 更新启动时间
    
    # 模拟关联启动
    for t in range(N):
        for i in range(N):
            if start_time[i] == t:
                # 更新相邻发动机的启动时间
                start_time[(i-1) % N] = min(start_time[(i-1) % N], t+1)
                start_time[(i+1) % N] = min(start_time[(i+1) % N], t+1)
    
    # 找出最后启动的时间
    last_start = max(start_time)
    
    # 统计并输出最后启动的发动机
    last_engines = [i for i in range(N) if start_time[i] == last_start]
    
    print(len(last_engines))
    print(*last_engines)

solve()

• C

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 10001

int min(int a, int b) {
    return a < b ? a : b;
}

int max(int a, int b) {
    return a > b ? a : b;
}

void solve() {
    int N, E;
    scanf("%d %d", &N, &E);
    
    // 初始化启动时间数组
    int start_time[MAX_N];
    for (int i = 0; i < N; i++) {
        start_time[i] = N + 1;
    }
    
    // 处理手动启动的输入
    for (int i = 0; i < E; i++) {
        int T, P;
        scanf("%d %d", &T, &P);
        start_time[P] = min(start_time[P], T);
    }
    
    // 模拟关联启动
    for (int t = 0; t < N; t++) {
        for (int i = 0; i < N; i++) {
            if (start_time[i] == t) {
                start_time[(i-1+N) % N] = min(start_time[(i-1+N) % N], t+1);
                start_time[(i+1) % N] = min(start_time[(i+1) % N], t+1);
            }
        }
    }
    
    // 找出最后启动的时间
    int last_start = 0;
    for (int i = 0; i < N; i++) {
        last_start = max(last_start, start_time[i]);
    }
    
    // 统计最后启动的发动机
    int count = 0;
    int last_engines[MAX_N];
    for (int i = 0; i < N; i++) {
        if (start_time[i] == last_start) {