机考E卷100分题 - 流浪地球
题目描述
流浪地球计划在赤道上均匀部署了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
123
输出
2
0 4
12
说明
8个发动机，时刻0启动2和6号发动机
示例2
输入：
8 2
0 0
1 7
123
输出：
1
4
12
说明
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); // 根据最早的激活时间开始更新状态
}
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
Python
def has_inactive_engines(engine_statuses):
"""检查列表中是否有引擎处于未激活状态（即状态为 -1）。
返回值为布尔类型，True表示存在未激活的引擎，False则表示所有引擎均已激活。"""
return -1 in engine_statuses
def 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 - 1
right_engine = 0 if current_engine == total_engines - 1 else current_engine + 1
if engine_statuses[left_engine] == -1:
engine_statuses[left_engine] = activation_time
if engine_statuses[right_engine] == -1:
engine_statuses[right_engine] = activation_time
def update_engine_statuses(engine_statuses, start_time):
"""更新所有引擎的激活状态，直到所有引擎都被激活。
进行循环检查，若当前时间点有引擎被激活，则激活其相邻引擎，并递增时间步长。"""
continue_update = True
while 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 += 1
continue_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 # 结束循环，等待输入结束
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
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()); // 输出激活的引擎索引
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
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;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
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;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384
大厂原题(全网最全，持续更新) 文章被收录于专栏
主要记录自己的刷题日常，学而时习之。
投递美团等公司6个岗位 >
滴滴公司福利 605人发布