当前位置：首页 > news >正文

【OD】【E卷】【真题】【100分】流浪地球（PythonJavaJavaScriptC++C）

news 2024/10/22 11:21:05

题目描述

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

初始状态下所有的发动机都是未启动状态;
发动机启动的方式分为”手动启动"和”关联启动"两种方式;
如果在时刻1一个发动机被启动，下一个时刻2与之相邻的两个发动机就会被”关联启动”;
如果准备启动某个发动机时，它已经被启动了，则什么都不用做;
发动机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号发动机

示例2

输入：

8 2
0 0
1 7

输出：

1
4

说明

8个发动机，时刻0手动启动0，时刻1手动启动7.

解题思路

题目解析

初始状态：所有的发动机都是未启动状态。
启动方式：
- 手动启动：你可以在某个时刻手动启动指定位置的发动机。
- 关联启动：如果一个发动机在时刻1被启动，那么它的相邻发动机（左右两个，位置编号上相邻）会在下一时刻（时刻2）被自动启动。
循环关系：发动机0和N-1是相邻的，这意味着整个发动机的排列是环形的。
发动机启动规则：
- 如果准备启动的发动机已经被启动，那么就不需要做任何操作。
- 需要根据手动启动的时刻和位置，推算出所有发动机何时被启动，并确定哪些发动机在最后一个时刻被启动。

用例图解

如图所示：

在时刻0，发动机2和6被手动启动。
在时刻1，发动机1、3、5、7将被关联启动。
到了时刻2，发动机0和4将被关联启动。
因此，发动机0和4是最后一批被启动的。

Java

import java.util.*;public class EngineManager {// 检查数组中是否有引擎处于未激活状态（即状态为 -1）public static boolean hasInactiveEngines(int[] engineStatuses) {return Arrays.stream(engineStatuses).anyMatch(status -> status == -1);}// 激活指定引擎的相邻引擎public static void activateAdjacentEngines(int[] engineStatuses, int currentEngine, int activationTime, int totalEngines) {int leftEngine = currentEngine == 0 ? totalEngines - 1 : (currentEngine - 1);  // 计算左边相邻引擎的索引int rightEngine = currentEngine == totalEngines - 1 ? 0 : currentEngine + 1;  // 计算右边相邻引擎的索引engineStatuses[leftEngine] = engineStatuses[leftEngine] == -1 ? activationTime : engineStatuses[leftEngine];  // 若左引擎未激活，则激活engineStatuses[rightEngine] = engineStatuses[rightEngine] == -1 ? activationTime : engineStatuses[rightEngine];  // 若右引擎未激活，则激活}// 更新所有引擎的激活状态，直到所有引擎都被激活public static void updateEngineStatuses(int[] engineStatuses, int startTime) {boolean continueUpdate = true;while (continueUpdate) {for (int i = 0; i < engineStatuses.length; i++) {if (engineStatuses[i] == startTime) {              activateAdjacentEngines(engineStatuses, i, startTime + 1, engineStatuses.length);  // 激活当前引擎的相邻引擎}}startTime++;  // 增加时间步长，检查下一个时间点continueUpdate = hasInactiveEngines(engineStatuses);  // 检查是否还有未激活的引擎}int lastActivationTime = Arrays.stream(engineStatuses).max().getAsInt();  // 获取最后一个被激活的时间int countActiveEngines = 0;StringBuilder enginesReport = new StringBuilder();for (int i = 0; i < engineStatuses.length; i++) {if(lastActivationTime == engineStatuses[i]) {enginesReport.append(i + " ");countActiveEngines++;}}System.out.println(countActiveEngines);  // 输出最后激活时间的引擎数量System.out.println(enginesReport.toString().trim());  // 输出这些引擎的编号}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNextLine()) {String[] inputs = scanner.nextLine().split(" ");int numberOfEngines = Integer.parseInt(inputs[0]);  // 引擎总数int numberOfEntries = Integer.parseInt(inputs[1]);  // 输入的数据条数int[] engineStatuses = new int[numberOfEngines];Arrays.fill(engineStatuses, -1);  // 初始状态设置所有引擎为未激活int earliestActivation = Integer.MAX_VALUE;for (int i = 0; i < numberOfEntries; i++) {String[] timeIndex = scanner.nextLine().split(" ");int activationTime = Integer.parseInt(timeIndex[0]);  // 激活时间int engineIndex = Integer.parseInt(timeIndex[1]);  // 引擎索引engineStatuses[engineIndex] = activationTime;  // 设置激活时间earliestActivation = Math.min(earliestActivation, activationTime);  // 记录最早的激活时间}updateEngineStatuses(engineStatuses, earliestActivation);  // 根据最早的激活时间开始更新状态}}
}

Python

def has_inactive_engines(engine_statuses):"""检查列表中是否有引擎处于未激活状态（即状态为 -1）。返回值为布尔类型，True表示存在未激活的引擎，False则表示所有引擎均已激活。"""return -1 in engine_statusesdef activate_adjacent_engines(engine_statuses, current_engine, activation_time, total_engines):"""激活指定引擎的相邻引擎。计算并更新左右两边的引擎状态。- current_engine: 当前引擎的索引。- activation_time: 当前引擎的激活时间。- total_engines: 引擎总数，用于计算边界条件。"""left_engine = total_engines - 1 if current_engine == 0 else current_engine - 1right_engine = 0 if current_engine == total_engines - 1 else current_engine + 1if engine_statuses[left_engine] == -1:engine_statuses[left_engine] = activation_timeif engine_statuses[right_engine] == -1:engine_statuses[right_engine] = activation_timedef update_engine_statuses(engine_statuses, start_time):"""更新所有引擎的激活状态，直到所有引擎都被激活。进行循环检查，若当前时间点有引擎被激活，则激活其相邻引擎，并递增时间步长。"""continue_update = Truewhile continue_update:for i, status in enumerate(engine_statuses):if status == start_time:        activate_adjacent_engines(engine_statuses, i, start_time + 1, len(engine_statuses))start_time += 1continue_update = has_inactive_engines(engine_statuses)last_activation_time = max(engine_statuses)count_active_engines = sum(status == last_activation_time for status in engine_statuses)engines_report = ' '.join(str(i) for i, status in enumerate(engine_statuses) if status == last_activation_time)print(count_active_engines)  # 打印在最后一个激活时间被激活的引擎数量print(engines_report.strip())  # 打印这些引擎的索引# 主循环，持续接受输入直到遇到文件结束符（EOF）
while True:try:inputs = input().split()number_of_engines = int(inputs[0])  # 读取引擎总数number_of_entries = int(inputs[1])  # 读取条目数量engine_statuses = [-1] * number_of_engines  # 初始化引擎状态数组，初始值为-1表示未激活earliest_activation = float('inf')  # 设置最早激活时间为无穷大for _ in range(number_of_entries):time_index = input().split()activation_time = int(time_index[0])engine_index = int(time_index[1])engine_statuses[engine_index] = activation_time  # 更新指定引擎的激活时间earliest_activation = min(earliest_activation, activation_time)  # 更新最早激活时间update_engine_statuses(engine_statuses, earliest_activation)  # 根据最早激活时间更新引擎状态except EOFError:break  # 结束循环，等待输入结束

JavaScript

// 引入 readline 模块并创建接口用于读取来自标准输入（stdin）的数据
const rl = require("readline").createInterface({ input: process.stdin });// 创建异步迭代器，用于按行读取输入
var iter = rl[Symbol.asyncIterator]();// 定义一个异步函数用于读取一行输入
const readline = async () => (await iter.next()).value;// 立即执行的异步函数
void (async function () {// 读取一行输入并按空格分割，获取输入的参数const inputs = (await readline()).split(" ");const numberOfEngines = parseInt(inputs[0], 10);  // 引擎总数const numberOfEntries = parseInt(inputs[1], 10);  // 输入的数据条数// 创建一个数组，初始值为 -1，表示所有引擎初始时都未激活const engineStatuses = new Array(numberOfEngines).fill(-1);let earliestActivation = Infinity;  // 设置一个变量用于记录最早的激活时间// 遍历每一个输入条目for (let i = 0; i < numberOfEntries; i++) {const timeIndex = (await readline()).split(" ");const activationTime = parseInt(timeIndex[0], 10);  // 读取激活时间const engineIndex = parseInt(timeIndex[1], 10);  // 读取引擎索引engineStatuses[engineIndex] = activationTime;  // 设置引擎的激活时间earliestActivation = Math.min(earliestActivation, activationTime);  // 更新最早的激活时间}// 根据最早的激活时间开始更新所有引擎的状态await updateEngineStatuses(engineStatuses, earliestActivation);process.exit(0);  // 执行完成后退出程序
})();// 检查是否有未激活的引擎
function hasInactiveEngines(engineStatuses) {return engineStatuses.some(status => status === -1);  // 使用 some 方法检查数组中是否存在未激活的引擎
}// 激活指定引擎的相邻引擎
function activateAdjacentEngines(engineStatuses, currentEngine, activationTime, totalEngines) {const leftEngine = currentEngine === 0 ? totalEngines - 1 : currentEngine - 1;  // 计算左侧相邻引擎的索引const rightEngine = currentEngine === totalEngines - 1 ? 0 : currentEngine + 1;  // 计算右侧相邻引擎的索引// 如果相邻引擎未激活，则设置其激活时间if (engineStatuses[leftEngine] === -1) {engineStatuses[leftEngine] = activationTime;}if (engineStatuses[rightEngine] === -1) {engineStatuses[rightEngine] = activationTime;}
}// 循环更新所有引擎的状态，直到没有未激活的引擎
async function updateEngineStatuses(engineStatuses, startTime) {let continueUpdate = true;while (continueUpdate) {for (let i = 0; i < engineStatuses.length; i++) {if (engineStatuses[i] === startTime) {activateAdjacentEngines(engineStatuses, i, startTime + 1, engineStatuses.length);}}startTime++;  // 增加时间步，继续检查和更新状态continueUpdate = hasInactiveEngines(engineStatuses);  // 检查是否还有未激活的引擎}const lastActivationTime = Math.max(...engineStatuses);  // 计算最后一个被激活的时间const countActiveEngines = engineStatuses.filter(status => status === lastActivationTime).length;  // 计算在最后一次激活时间激活的引擎数量const enginesReport = engineStatuses.map((status, index) => status === lastActivationTime ? index : '').filter(String).join(' ');  // 创建引擎索引报告console.log(countActiveEngines);  // 输出激活的引擎数量console.log(enginesReport.trim());  // 输出激活的引擎索引
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <limits>
using namespace std;// 检查 vector 中是否有引擎处于未激活状态（即状态为 -1）
bool hasInactiveEngines(const vector<int>& engineStatuses) {return find(engineStatuses.begin(), engineStatuses.end(), -1) != engineStatuses.end();
}// 激活指定引擎的相邻引擎
void activateAdjacentEngines(vector<int>& engineStatuses, int currentEngine, int activationTime, int totalEngines) {int leftEngine = currentEngine == 0 ? totalEngines - 1 : currentEngine - 1; // 计算左边相邻引擎的索引int rightEngine = currentEngine == totalEngines - 1 ? 0 : currentEngine + 1; // 计算右边相邻引擎的索引if (engineStatuses[leftEngine] == -1) {engineStatuses[leftEngine] = activationTime; // 若左引擎未激活，则激活}if (engineStatuses[rightEngine] == -1) {engineStatuses[rightEngine] = activationTime; // 若右引擎未激活，则激活}
}// 更新所有引擎的激活状态，直到所有引擎都被激活
void updateEngineStatuses(vector<int>& engineStatuses, int startTime) {bool continueUpdate = true;while (continueUpdate) {for (size_t i = 0; i < engineStatuses.size(); i++) {if (engineStatuses[i] == startTime) {activateAdjacentEngines(engineStatuses, i, startTime + 1, engineStatuses.size()); // 激活当前引擎的相邻引擎}}startTime++; // 增加时间步长，检查下一个时间点continueUpdate = hasInactiveEngines(engineStatuses); // 检查是否还有未激活的引擎}int lastActivationTime = *max_element(engineStatuses.begin(), engineStatuses.end()); // 获取最后一个被激活的时间int countActiveEngines = count(engineStatuses.begin(), engineStatuses.end(), lastActivationTime); // 计算最后激活时间的引擎数量cout << countActiveEngines << endl; // 输出最后激活时间的引擎数量for (size_t i = 0; i < engineStatuses.size(); i++) {if (engineStatuses[i] == lastActivationTime) {cout << i << " "; // 输出最后激活时间的引擎编号}}cout << endl;
}int main() {string input;while (getline(cin, input)) {stringstream ss(input);int numberOfEngines, numberOfEntries;ss >> numberOfEngines >> numberOfEntries;vector<int> engineStatuses(numberOfEngines, -1); // 初始状态设置所有引擎为未激活int earliestActivation = numeric_limits<int>::max(); // 设置最早的激活时间为最大值for (int i = 0; i < numberOfEntries; i++) {getline(cin, input);stringstream ss2(input);int activationTime, engineIndex;ss2 >> activationTime >> engineIndex;engineStatuses[engineIndex] = activationTime; // 设置激活时间earliestActivation = min(earliestActivation, activationTime); // 更新最早的激活时间}updateEngineStatuses(engineStatuses, earliestActivation); // 根据最早的激活时间开始更新状态}return 0;
}

C语言

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>// 检查数组中是否有引擎处于未激活状态（即状态为 -1）
int hasInactiveEngines(int *engineStatuses, int totalEngines) {for (int i = 0; i < totalEngines; i++) {if (engineStatuses[i] == -1) {return 1;  // 发现未激活的引擎，返回1表示"真"}}return 0;  // 所有引擎都已激活，返回0表示"假"
}// 激活指定引擎的相邻引擎
void activateAdjacentEngines(int *engineStatuses, int currentEngine, int activationTime, int totalEngines) {int leftEngine = currentEngine == 0 ? totalEngines - 1 : currentEngine - 1;  // 计算左边相邻引擎的索引int rightEngine = currentEngine == totalEngines - 1 ? 0 : currentEngine + 1;  // 计算右边相邻引擎的索引if (engineStatuses[leftEngine] == -1) {engineStatuses[leftEngine] = activationTime;  // 若左引擎未激活，则激活}if (engineStatuses[rightEngine] == -1) {engineStatuses[rightEngine] = activationTime;  // 若右引擎未激活，则激活}
}// 更新所有引擎的激活状态，直到所有引擎都被激活
void updateEngineStatuses(int *engineStatuses, int startTime, int totalEngines) {int continueUpdate = 1;while (continueUpdate) {for (int i = 0; i < totalEngines; i++) {if (engineStatuses[i] == startTime) {activateAdjacentEngines(engineStatuses, i, startTime + 1, totalEngines);  // 激活当前引擎的相邻引擎}}startTime++;  // 增加时间步长，检查下一个时间点continueUpdate = hasInactiveEngines(engineStatuses, totalEngines);  // 检查是否还有未激活的引擎}int lastActivationTime = -1;int countActiveEngines = 0;for (int i = 0; i < totalEngines; i++) {if (engineStatuses[i] > lastActivationTime) {lastActivationTime = engineStatuses[i];  // 更新最后一个被激活的时间}}for (int i = 0; i < totalEngines; i++) {if (engineStatuses[i] == lastActivationTime) {countActiveEngines++;  // 计算最后激活时间的引擎数量}}printf("%d\n", countActiveEngines);  // 输出最后激活时间的引擎数量for (int i = 0; i < totalEngines; i++) {if (engineStatuses[i] == lastActivationTime) {printf("%d ", i);  // 输出这些引擎的编号}}printf("\n");
}int main() {char line[1024];while (fgets(line, sizeof(line), stdin)) {  // 从标准输入读取一行int numberOfEngines, numberOfEntries;sscanf(line, "%d %d", &numberOfEngines, &numberOfEntries);  // 解析引擎总数和输入的数据条数int *engineStatuses = (int *)malloc(numberOfEngines * sizeof(int));memset(engineStatuses, -1, numberOfEngines * sizeof(int));  // 初始状态设置所有引擎为未激活int earliestActivation = INT_MAX;for (int i = 0; i < numberOfEntries; i++) {fgets(line, sizeof(line), stdin);  // 读取每个激活信息int activationTime, engineIndex;sscanf(line, "%d %d", &activationTime, &engineIndex);  // 解析激活时间和引擎索引engineStatuses[engineIndex] = activationTime;  // 设置激活时间if (activationTime < earliestActivation) {earliestActivation = activationTime;  // 更新最早的激活时间}}updateEngineStatuses(engineStatuses, earliestActivation, numberOfEngines);  // 根据最早的激活时间开始更新状态free(engineStatuses);  // 释放动态分配的内存}return 0;
}