E卷-流浪地球(100分)

流浪地球

问题描述

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

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) {
            last_engines[count++] = i;
        }
    }
    
    // 输出结果
    printf("%d\n", count);
    for (int i = 0; i < count; i++) {
        printf("%d ", last_engines[i]);
    }
    printf("\n");
}

int main() {
    solve();
    return 0;
}

• Javascript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lines = [];

rl.on('line', (line) => {
    lines.push(line);
});

rl.on('close', () => {
    solve(lines);
});

function solve(lines) {
    // 解析输入
    const [N, E] = lines[0].split(' ').map(Number);
    
    // 初始化启动时间数组
    const startTime = new Array(N).fill(10 * N + 1);
    
    // 处理手动启动的输入
    for (let i = 1; i <= E; i++) {
        const [T, P] = lines[i].split(' ').map(Number);
        startTime[P] = Math.min(startTime[P], T);
    }
    
    // 模拟关联启动
    for (let t = 0; t < N; t++) {
        for (let i = 0; i < N; i++) {
            if (startTime[i] === t) {
                startTime[(i-1+N) % N] = Math.min(startTime[(i-1+N) % N], t+1);
                startTime[(i+1) % N] = Math.min(startTime[(i+1) % N], t+1);
            }
        }
    }
    
    // 找出最后启动的时间
    const lastStart = Math.max(...startTime);
    
    // 统计并输出最后启动的发动机
    const lastEngines = startTime.reduce((acc, time, index) => {
        if (time === lastStart) acc.push(index);
        return acc;
    }, []);
    
    console.log(lastEngines.length);
    console.log(lastEngines.join(' '));
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int E = scanner.nextInt();
        
        // 初始化启动时间数组
        int[] startTime = new int[N];
        Arrays.fill(startTime, N * 10 + 1);
        
        // 处理手动启动的输入
        for (int i = 0; i < E; i++) {
            int T = scanner.nextInt();
            int P = scanner.nextInt();
            startTime[P] = Math.min(startTime[P], T);
        }
        
        // 模拟关联启动
        for (int t = 0; t < N; t++) {
            for (int i = 0; i < N; i++) {
                if (startTime[i] == t) {
                    startTime[(i-1+N) % N] = Math.min(startTime[(i-1+N) % N], t+1);
                    startTime[(i+1) % N] = Math.min(startTime[(i+1) % N], t+1);
                }
            }
        }
        
        // 找出最后启动的时间
        int lastStart = Arrays.stream(startTime).max().getAsInt();
        
        // 统计并输出最后启动的发动机
        List<Integer> lastEngines = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            if (startTime[i] == lastStart) {
                lastEngines.add(i);
            }
        }
        
        System.out.println(lastEngines.size());
        for (int engine : lastEngines) {
            System.out.print(engine + " ");
        }
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int N, E;
    cin >> N >> E;
    
    // 初始化启动时间数组
    vector<int> start_time(N, 10 * N + 1);
    
    // 处理手动启动的输入
    for (int i = 0; i < E; i++) {
        int T, P;
        cin >> 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 = *max_element(start_time.begin(), start_time.end());
    
    // 统计并输出最后启动的发动机
    vector<int> last_engines;
    for (int i = 0; i < N; i++) {
        if (start_time[i] == last_start) {
            last_engines.push_back(i);
        }
    }
    
    cout << last_engines.size() << endl;
    for (int engine : last_engines) {
        cout << engine << " ";
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    solve();
    
    return 0;
}