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

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

article 2024/10/20 19:07:47

题目描述

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

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

    • 手动启动：你可以在某个时刻手动启动指定位置的发动机。
    • 关联启动：如果一个发动机在时刻1被启动，那么它的相邻发动机（左右两个，位置编号上相邻）会在下一时刻（时刻2）被自动启动。

  3. 循环关系：发动机0和N-1是相邻的，这意味着整个发动机的排列是环形的。

  4. 发动机启动规则：

    • 如果准备启动的发动机已经被启动，那么就不需要做任何操作。
    • 需要根据手动启动的时刻和位置，推算出所有发动机何时被启动，并确定哪些发动机在最后一个时刻被启动。

用例图解

如图所示：

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

image-20240817105929077

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_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  # 结束循环，等待输入结束

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;
}

http://www.kler.cn/news/357678.html

相关文章：

  • [论文笔记] Megatron LM环境安装
  • 如何查看默认网关地址：详细步骤
  • 高级大数据工程师带你一起学习Hdoop生态Flink基础原理保姆级教程
  • Docker 安装达梦 DM8 数据库实战指南
  • 使用 Dijkstra 算法优化物流配送路径
  • 文献分享: 高维ANN算法的综述
  • 【Flutter】Dart：变量和内置类型
  • Java 直接获取 pom.xml 配置的属性值
  • 【0day】ChatGPT个人专用版 pictureproxy SSRF漏洞【附poc下载】
  • 15.java面向对象：多态
  • 可达性分析法
  • 2024-10-15 Nuxt3打包部署到Nginx流程
  • [LeetCode] 210. 课程表II
  • 对Android的Binder机制的了解
  • 汽车建模用什么软件最好？汽车建模渲染建议！
  • 【力扣 | SQL题 | 每日4题】力扣2308，2324，2346，2372
  • 特斯联|日常|Java|后端开发
  • LeetCode LRU 缓存
  • MySQL创建和管理表
  • 第15篇：网络架构优化与综合案例分析