【华为OD-E卷-04 流浪地球 100分（python、java、c++、js、c）】

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为OD-E卷-流浪地球 100分（python、java、c++、js、c）】

题目

流浪地球计划在赤道上均匀部署了 N 个转向发动机，按位置顺序编号为 0 ~ N
初始状态下所有的发动机都是未启动状态 发动机启动的方式分为“手动启动”和“关联启动”两种方式 如果在时刻 1 一个发动机被启动，下一个时刻 2 与之相邻的两个发动机就会被“关联启动” 如果准备启动某个发动机时，它已经被启动了，则什么都不用做 发动机 0 与发动机 N-1 是相邻的 地球联合政府准备挑选某些发动机在某些时刻进行“手动启动”。当然最终所有的发动机都会被启动。哪些发动机最晚被启动呢？

输入描述

  • 第一行两个数字 N 和 E，中间有空格

N 代表部署发动机的总个数，1 < N ≤ 1000 E 代表计划手动启动的发动机总个数，1 ≤ E ≤ 1000，E ≤ N 接下来共 E 行，每行都是两个数字 T 和 P，中间有空格

T 代表发动机的手动启动时刻，0 ≤ T ≤ N P 代表次发动机的位置编号，0 ≤ P < N

输出描述

  • 第一行一个数字 N， 以回车结束

N 代表最后被启动的发动机个数 第二行 N 个数字，中间有空格，以回车结束

每个数字代表发动机的位置编号，从小到大排序

用例

用例一：
输入：
8 2
0 2
0 6
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
输出：
2
0 4
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2

python解法

  • 解题思路：
  • 这道题目给定了多个发动机，每个发动机可以手动启动。对于每个发动机的位置，存在一定的“启动时间”。然后，对于每个发动机，它的启动时间可以由距离已经启动的发动机的时间来推导。如果一个发动机启动了，它可以影响周围位置的发动机启动时间，按照一定的规则（按距离影响）。

输入解析：

num_engines 表示发动机的数量。
manual_starts 表示手动启动的发动机的数量。
接下来是一些手动启动的发动机的信息，包括它们的启动时间和位置。
处理启动时间：

我们维护一个 start_times 数组来记录每个发动机的启动时间，初始化为 inf（表示尚未启动）。
对于每个手动启动的发动机，我们更新它的启动时间。
传播启动时间：

然后，我们根据已经启动的发动机来更新其他发动机的启动时间。通过计算发动机之间的距离，可以传播最小的启动时间。由于这些发动机在一个环形排列的道路上，可以通过“最短距离”来更新它们的启动时间。
确定最后启动的发动机：

计算最终所有发动机的启动时间，并找到启动时间最大的发动机。若有多个发动机具有相同的最大启动时间，所有这些发动机的编号都要输出。
输出结果：

输出最后启动的发动机的数量和它们的编号（按升序排列）。

# 读取输入数据，num_engines表示发动机数量，manual_starts表示手动启动的发动机数量
num_engines, manual_starts = map(int, input().split())

# 初始化启动时间为正无穷，表示初始状态下所有发动机都没有启动
start_times = [float('inf')] * num_engines

# 处理手动启动的发动机，更新对应发动机的启动时间
for _ in range(manual_starts):
    time, position = map(int, input().split())
    start_times[position] = time  # 更新该位置发动机的启动时间

# 对于每个发动机，传播启动时间
for i in range(num_engines):
    for j in range(num_engines):
        # 计算发动机i与j之间的最短距离，考虑环形路径
        distance = min(abs(i - j), num_engines - abs(i - j))
        # 更新发动机j的启动时间，取最小值
        start_times[j] = min(start_times[j], start_times[i] + distance)

# 找到最后启动的发动机，记录它们的启动时间
max_time = -1
last_started = []

# 遍历所有发动机，找到启动时间最大（最后启动）的发动机
for pos in range(num_engines):
    time = start_times[pos]
    if time > max_time:
        max_time = time  # 更新最大启动时间
        last_started = [pos]  # 重新开始记录最后启动的发动机
    elif time == max_time:
        last_started.append(pos)  # 如果启动时间相同，则加入该发动机

# 对最后启动的发动机位置按升序排序
last_started.sort()

# 输出最后启动的发动机数量和它们的编号（从0开始编号）
print(len(last_started))
print(" ".join(map(str, last_started)))

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

java解法

  • 解题思路
  • 该题的核心是模拟一个环形布局的发动机启动问题，每个发动机可以通过相邻发动机的影响来启动。具体来说，给定某些发动机的启动时间，其他发动机的启动时间将通过传播来更新。我们需要模拟这个传播过程，并最终确定最后启动的发动机。

输入解析：

n 表示发动机的数量。
e 表示手动启动的发动机数量。
接下来的输入包括每个手动启动的发动机的启动时间和位置。
数据结构：

startTimes 数组：记录每个发动机的启动时间，初始时所有发动机的启动时间为 -1（表示未启动）。
queue 队列：用于按顺序传播启动时间，存储启动时间和对应发动机的位置。
传播过程：

对于每个已经启动的发动机，它会影响其相邻的发动机（左邻居和右邻居）。若相邻的发动机尚未启动，则将它们的启动时间设置为当前发动机的启动时间加 1，并将这些发动机加入队列继续传播。
由于是环形结构，相邻的发动机在数组边界处会“环绕”，即左邻居是 (pos - 1 + n) % n，右邻居是 (pos + 1) % n。
找出最后启动的发动机：

在传播完成后，遍历所有发动机，找到启动时间最大的发动机，并输出这些发动机的位置（按升序排列）。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入：n 表示发动机数量，e 表示手动启动的发动机数量
        int n = scanner.nextInt();
        int e = scanner.nextInt();

        // 初始化启动时间数组，初始值为 -1（表示尚未启动）
        int[] startTimes = new int[n];
        Arrays.fill(startTimes, -1);

        // 使用队列来进行广度优先搜索（BFS）传播启动时间
        Queue<int[]> queue = new LinkedList<>();
        
        // 读取手动启动的发动机信息，并设置启动时间
        for (int i = 0; i < e; i++) {
            int time = scanner.nextInt();
            int position = scanner.nextInt();
            queue.offer(new int[]{time, position});
            startTimes[position] = time; // 设置手动启动的发动机启动时间
        }

        // 开始传播过程
        while (!queue.isEmpty()) {
            int[] current = queue.poll(); // 取出当前启动的发动机
            int time = current[0] + 1;  // 当前发动机启动时间加 1，即传播的时间
            int pos = current[1]; // 当前发动机的位置

            // 计算环形结构中的左邻居和右邻居
            int leftNeighbor = (pos - 1 + n) % n;
            int rightNeighbor = (pos + 1) % n;

            // 如果左邻居尚未启动，则设置其启动时间并加入队列
            if (startTimes[leftNeighbor] == -1) {
                startTimes[leftNeighbor] = time;
                queue.offer(new int[]{time, leftNeighbor});
            }

            // 如果右邻居尚未启动，则设置其启动时间并加入队列
            if (startTimes[rightNeighbor] == -1) {
                startTimes[rightNeighbor] = time;
                queue.offer(new int[]{time, rightNeighbor});
            }
        }

        // 找到最后启动的发动机的最大启动时间
        int maxTime = Arrays.stream(startTimes).max().getAsInt();
        
        // 存储所有最后启动的发动机位置
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (startTimes[i] == maxTime) {
                result.add(i); // 记录最后启动的发动机位置
            }
        }

        // 输出最后启动的发动机的数量
        System.out.println(result.size());

        // 输出最后启动的发动机的位置（按升序排列）
        for (int i = 0; i < result.size(); i++) {
            if (i != 0) {
                System.out.print(" ");
            }
            System.out.print(result.get(i)); // 输出发动机位置
        }
        System.out.println(); // 换行，确保输出格式正确
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C++解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C解法

步骤分析：

输入解析：

numEngines 表示发动机的数量。
manualStarts 表示手动启动的发动机数量。
接下来的输入中，我们获得每个手动启动的发动机的启动时间和位置。
初始化：

用一个数组 activationTimes 来记录每个发动机的启动时间，初始化为 INT_MAX，表示这些发动机还没有启动。
手动启动：

对于每个手动启动的发动机，直接将其启动时间更新到数组中。
传播启动时间：

使用一个模拟的传播过程。对每个时间 t，遍历所有发动机。如果某个发动机在时间 t 启动，那么它的左右相邻发动机将在时间 t + 1 启动。如果这些相邻发动机的启动时间未被设置过（即仍为 INT_MAX），则更新其启动时间。
传播过程会持续直到没有更多的发动机可以被启动。
找出最后启动的发动机：

遍历 activationTimes 数组，找出最大的启动时间 latestTime。
然后遍历一次 activationTimes 数组，找出所有在 latestTime 启动的发动机并记录它们的位置。
输出结果：

输出最后启动的发动机的数量。
输出最后启动的发动机的编号。

#include 
#include 
#include 

int main() {
    int numEngines, manualStarts;
    
    // 读取输入的发动机数量和手动启动的数量
    scanf("%d %d", &numEngines, &manualStarts);

    // 初始化发动机的启动时间数组，初始值为 INT_MAX，表示尚未启动
    int activationTimes[numEngines];
    for (int i = 0; i < numEngines; i++) {
        activationTimes[i] = INT_MAX;  // 使用 INT_MAX 来表示尚未启动
    }

    // 读取手动启动的发动机的信息，并设置其启动时间
    for (int i = 0; i < manualStarts; i++) {
        int time, pos;
        scanf("%d %d", &time, &pos);  // 读取启动时间和启动位置
        activationTimes[pos] = time;  // 设置该发动机的启动时间
    }

    // 模拟传播启动时间
    // 运行最多 numEngines 次来传播启动时间（可以认为这就是传播的最大可能步数）
    for (int t = 0; t <= numEngines; t++) {
        for (int i = 0; i < numEngines; i++) {
            if (activationTimes[i] == t) {  // 如果发动机 i 在时间 t 启动
                // 计算左邻居和右邻居的位置（环形结构）
                int left = (i - 1 + numEngines) % numEngines;
                int right = (i + 1) % numEngines;

                // 如果左邻居尚未启动，则设置它的启动时间为 t+1
                if (activationTimes[left] > t + 1) {
                    activationTimes[left] = t + 1;
                }

                // 如果右邻居尚未启动，则设置它的启动时间为 t+1
                if (activationTimes[right] > t + 1) {
                    activationTimes[right] = t + 1;
                }
            }
        }
    }

    // 找出最后启动的时间
    int latestTime = 0;
    for (int i = 0; i < numEngines; i++) {
        if (activationTimes[i] > latestTime) {  // 找到最大的启动时间
            latestTime = activationTimes[i];
        }
    }

    // 统计并记录最后启动的发动机数量及其位置
    int count = 0;
    for (int i = 0; i < numEngines; i++) {
        if (activationTimes[i] == latestTime) {
            count++;  // 统计最后启动的发动机数量
        }
    }

    // 输出最后启动的发动机数量
    printf("%d\n", count);

    // 输出最后启动的发动机的位置（按升序排列）
    for (int i = 0; i < numEngines; i++) {
        if (activationTimes[i] == latestTime) {
            printf("%d ", i);  // 输出最后启动的发动机编号
        }
    }
    printf("\n");

    return 0;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

JS解法

主要步骤：

初始化：

读取输入的发动机数量 numEngines 和手动启动的发动机数量 manualStarts。
初始化一个数组 activationTimes，用来记录每个发动机的启动时间，初始值设为 Infinity（表示尚未启动）。
处理手动启动：

对每一个手动启动的发动机，直接更新对应位置的启动时间。
传播启动时间：

通过 BFS（广度优先搜索）模拟启动时间的传播。
从所有已知启动的发动机开始，逐步更新它们左右相邻发动机的启动时间，直到没有更多的发动机可以被更新。
找出最后启动的发动机：

计算出所有发动机中的最大启动时间。
找出所有启动时间等于最大时间的发动机，按升序输出它们的编号。

const readline = require("readline");

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

let inputs = [];  // 用来存储输入数据
let manualStarts = 0;  // 记录手动启动的发动机数量

// 监听每一行输入
rl.on("line", (line) => {
    // 第一行输入包含发动机数量和手动启动的数量
    if (inputs.length === 0) {
        const [numEngines, starts] = line.split(" ").map(Number);
        manualStarts = starts;
        // 初始化输入数据结构
        inputs.push({ numEngines, manualStarts, activationTimes: Array(numEngines).fill(Infinity) });
    } else {
        // 对于每个手动启动的发动机，更新启动时间
        const [time, pos] = line.split(" ").map(Number);
        const { activationTimes } = inputs[0];  // 获取当前的启动时间数组
        activationTimes[pos] = time;

        // 如果所有手动启动的发动机已经被处理
        if (inputs[0].activationTimes.filter(t => t !== Infinity).length === manualStarts) {
            activateEngines(inputs[0].numEngines, activationTimes);  // 开始激活发动机
        }
    }
});

// 激活所有发动机的函数
function activateEngines(numEngines, activationTimes) {
    const queue = [];  // 使用队列来进行广度优先搜索（BFS）

    // 将所有已经手动启动的发动机放入队列
    for (let i = 0; i < numEngines; i++) {
        if (activationTimes[i] !== Infinity) {
            queue.push(i);
        }
    }

    // BFS过程，传播启动时间
    while (queue.length > 0) {
        const current = queue.shift();  // 获取当前正在传播的发动机
        const neighbors = [
            (current - 1 + numEngines) % numEngines,  // 左邻居
            (current + 1) % numEngines               // 右邻居
        ];

        // 对左右邻居进行时间更新
        neighbors.forEach(neighbor => {
            // 如果邻居尚未启动，或者启动时间可以被更新
            if (activationTimes[neighbor] > activationTimes[current] + 1) {
                activationTimes[neighbor] = activationTimes[current] + 1;
                queue.push(neighbor);  // 将更新过的邻居加入队列，继续传播
            }
        });
    }

    // 找出最大的启动时间
    const latestTime = Math.max(...activationTimes);

    const lastEngines = [];
    // 找到所有在最大启动时间时启动的发动机
    for (let i = 0; i < numEngines; i++) {
        if (activationTimes[i] === latestTime) {
            lastEngines.push(i);
        }
    }

    // 输出结果：最后启动的发动机数量
    console.log(lastEngines.length);
    // 输出最后启动的发动机编号（按升序排列）
    console.log(lastEngines.sort((a, b) => a - b).join(" "));
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/144512577"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！