E卷-流浪地球(100分)
流浪地球
问题描述
流浪地球计划在赤道上均匀部署了 个转向发动机,按位置顺序编号为 到 。
- 初始状态下所有的发动机都是未启动状态;
- 发动机起动的方式分为"手动启动"和"关联启动"两种方式;
- 如果在时刻 一个发动机被启动,下一个时刻 与之相邻的两个发动机就会被"关联启动";
- 如果准备启动某个发动机时,它已经被启动了,则什么都不用做;
- 发动机 与发动机 是相邻的。
地球联合政府准备挑选某些发动机在某些时刻进行"手动启动",当然最终所有的发动机都会被启动。哪些发动机最晚被启动呢?
输入格式
第一行包含两个整数 和 ,用空格分隔。
- 代表部署发动机的总个数
- 代表计划手动启动的发动机总个数
- ,,
接下来共 行,每行包含两个整数 和 ,用空格分隔。
- 代表发动机的手动启动时刻
- 代表此发动机的位置编号
- ,
输出格式
第一行输出一个整数 ,表示最后被启动的发动机个数。
第二行输出 个整数,表示最后被启动的发动机的位置编号,从小到大排序,用空格分隔。
样例输入 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 号发动机。
数据范围
题解
这道题目可以通过模拟发动机启动过程来解决。
使用一个数组来记录每个发动机的启动时间,初始化为一个足够大的值表示未启动。然后按照输入的顺序模拟手动启动和关联启动的过程。
具体步骤如下:
- 初始化一个长度为 的数组
start_time
,所有元素设为一个较大的数字。 - 对于每次手动启动,更新对应发动机的启动时间。
- 模拟关联启动:从时刻 0 到 ,检查每个发动机,如果它在当前时刻启动,则更新其相邻两个发动机的启动时间(如果尚未启动)。
- 遍历
start_time
数组,找出最大的启动时间,这就是最后启动的时间。 - 再次遍历数组,统计并输出启动时间等于最大启动时间的发动机编号。
这种方法的时间复杂度为 ,空间复杂度为 。对于给定的数据范围,这个解法是足够的。
参考代码
以下是五种语言的实现,都包含了详细的注释:
- 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;
}
#OD##OD机考##E卷#OD刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记