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

【2024年华为OD机试】 (B卷,100分)- 流水线（Java JS PythonC/C++）

article 2025/1/19 20:58:35

在这里插入图片描述

一、问题描述

题目描述

一个工厂有 m 条流水线，来并行完成 n 个独立的作业，该工厂设置了一个调度系统，在安排作业时，总是优先执行处理时间最短的作业。

现给定流水线个数 m，需要完成的作业数 n，每个作业的处理时间分别为 t1, t2, ..., tn。请你编程计算处理完所有作业的耗时为多少？

当 n > m 时，首先处理时间短的 m 个作业进入流水线，其他的等待，当某个作业完成时，依次从剩余作业中取处理时间最短的进入处理。

输入描述

第一行为2个整数（采用空格分隔），分别表示流水线个数 m 和作业数 n；

第二行输入 n 个整数（采用空格分隔），表示每个作业的处理时长 t1, t2, ..., tn。

  • 0 < m, n < 100
  • 0 < t1, t2, ..., tn < 100

注：保证输入都是合法的。

输出描述

输出处理完所有作业的总时长。

用例

用例 1

输入:

3 5
8 4 3 2 10

输出:

13

题目解析

简单的逻辑题。解题思路如下：

题目说“总是优先执行处理时间最短的作业”，因此我们可以将 8 4 3 2 10 进行升序排序变为 2 3 4 8 10，然后依次将排序后元素投入对应流水线中，如下图所示：

流水线1: 2 -> 8 -> 10 (总耗时: 2 + 8 + 10 = 20)
流水线2: 3 -> 10 (总耗时: 3 + 10 = 13)
流水线3: 4 (总耗时: 4)

计算每条流水线的时间总和，最大的那个就是题解。

详细步骤

  1. 读取输入：

    • 读取流水线个数 m 和作业数 n。
    • 读取每个作业的处理时间 t1, t2, ..., tn。

  2. 排序：

    • 将作业处理时间按升序排序。

  3. 初始化流水线：

    • 创建一个数组 lines，长度为 m，初始化为 0，表示每条流水线的当前总耗时。

  4. 分配作业：

    • 遍历排序后的作业处理时间，依次将作业分配到当前总耗时最小的流水线中。
    • 更新该流水线的总耗时。

  5. 输出结果：

    • 输出所有流水线中最大总耗时。

用例解释

用例 1
  • 输入：
    • m = 3
    • n = 5
    • t = [8, 4, 3, 2, 10]
  • 输出：
    • 13

解释：

  • 排序后的作业处理时间：[2, 3, 4, 8, 10]
  • 分配作业：
    • 流水线1: 2 -> 8 -> 10 (总耗时: 2 + 8 + 10 = 20)
    • 流水线2: 3 -> 10 (总耗时: 3 + 10 = 13)
    • 流水线3: 4 (总耗时: 4)
  • 最大总耗时为 13，因此输出 13。
    在这里插入图片描述

通过上述步骤，我们可以高效地计算处理完所有作业的总时长。这种方法的时间复杂度主要由排序操作决定，为 O(n log n)，其中 n 是作业数。

二、JavaScript算法源码

以下是 JavaScript 代码 的详细中文注释和讲解：

JavaScript 代码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline"); // 引入 readline 模块，用于读取控制台输入

// 创建 readline 接口实例
const rl = readline.createInterface({
  input: process.stdin,  // 输入流为标准输入
  output: process.stdout, // 输出流为标准输出
});

const lines = []; // 定义一个数组 lines，用于存储输入的行数据

// 监听 'line' 事件，每次读取一行输入
rl.on("line", (line) => {
  lines.push(line); // 将当前行数据存入 lines 数组

  // 当 lines 数组中有 2 行数据时，开始处理输入
  if (lines.length === 2) {
    // 解析第一行输入
    let [m, n] = lines[0].split(" ").map((ele) => parseInt(ele)); // 将第一行按空格分割，并转换为整数
    // 解析第二行输入
    let times = lines[1]
      .split(" ") // 将第二行按空格分割
      .slice(0, n) // 只取前 n 个元素
      .map((ele) => parseInt(ele)); // 将每个元素转换为整数

    times.sort((a, b) => a - b); // 对 times 数组进行升序排序

    let mArr = new Array(m).fill(0); // 创建一个长度为 m 的数组 mArr，初始值为 0

    // 遍历 times 数组，将每个任务分配给当前负载最小的机器
    times.forEach((time, idx) => {
      mArr[idx % m] += time; // 将任务分配给 idx % m 号机器
    });

    console.log(Math.max(...mArr)); // 输出 mArr 数组中的最大值，即所有机器中最大的负载

    lines.length = 0; // 清空 lines 数组，为下一次输入做准备
  }
});

代码讲解：

1. 输入部分：
  • readline 模块：
    • 使用 readline 模块读取控制台输入。
    • 通过 rl.on("line", ...) 监听每一行输入。
  • lines 数组：
    • 用于存储输入的行数据。
    • 当 lines 数组中有 2 行数据时，开始处理输入。
2. 数据处理部分：
  • 解析第一行输入：
    • 使用 split(" ") 将第一行按空格分割。
    • 使用 map((ele) => parseInt(ele)) 将分割后的字符串转换为整数。
    • 提取 m（机器数量）和 n（任务数量）。
  • 解析第二行输入：
    • 使用 split(" ") 将第二行按空格分割。
    • 使用 slice(0, n) 只取前 n 个元素。
    • 使用 map((ele) => parseInt(ele)) 将分割后的字符串转换为整数。
  • 排序：
    • 对 times 数组进行升序排序，确保任务按时间从小到大分配。
3. 任务分配部分：
  • mArr 数组：
    • 创建一个长度为 m 的数组 mArr，初始值为 0。
    • 用于记录每台机器的总负载。
  • 任务分配逻辑：
    • 遍历 times 数组，将每个任务分配给当前负载最小的机器。
    • 使用 idx % m 实现轮询分配。
4. 输出部分：
  • Math.max(...mArr)：
    • 计算 mArr 数组中的最大值，即所有机器中最大的负载。
    • 使用 console.log 输出结果。
5. 清空 lines 数组：
  • 在处理完当前输入后，清空 lines 数组，为下一次输入做准备。

示例运行：

输入 1：
3 5
1 2 3 4 5
  • 输出：
    7
  • 解释：
    • m = 3（3 台机器），n = 5（5 个任务）。
    • 任务时间数组为 [1, 2, 3, 4, 5]。
    • 分配结果：
      • 机器 0：1 + 4 = 5
      • 机器 1：2 + 5 = 7
      • 机器 2：3 = 3
    • 最大负载为 7。
输入 2：
2 4
3 1 7 2
  • 输出：
    8
  • 解释：
    • m = 2（2 台机器），n = 4（4 个任务）。
    • 任务时间数组为 [1, 2, 3, 7]（排序后）。
    • 分配结果：
      • 机器 0：1 + 7 = 8
      • 机器 1：2 + 3 = 5
    • 最大负载为 8。

总结：

  • 该代码通过轮询分配的方式，将任务分配给负载最小的机器。
  • 使用 readline 模块读取控制台输入，并动态处理输入数据。
  • 如果有其他问题，欢迎继续提问！

三、Java算法源码

以下是 Java 代码 的详细中文注释和讲解：

Java 代码

import java.util.Arrays; // 导入 Arrays 工具类，用于数组排序和流操作
import java.util.Scanner; // 导入 Scanner 类，用于读取控制台输入

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in); // 创建 Scanner 对象，用于读取输入

    int m = sc.nextInt(); // 读取机器数量 m
    int n = sc.nextInt(); // 读取任务数量 n

    int[] times = new int[n]; // 定义数组 times，用于存储每个任务的执行时间
    for (int i = 0; i < n; i++) times[i] = sc.nextInt(); // 读取每个任务的执行时间并存入 times 数组

    System.out.println(getResult(m, n, times)); // 调用 getResult 方法计算结果并输出
  }

  /**
   * 计算所有机器中最大的负载
   * @param m 机器数量
   * @param n 任务数量
   * @param times 每个任务的执行时间数组
   * @return 所有机器中最大的负载
   */
  public static int getResult(int m, int n, int[] times) {
    Arrays.sort(times); // 对任务执行时间数组进行升序排序

    int[] mArr = new int[m]; // 定义数组 mArr，用于记录每台机器的总负载
    for (int i = 0; i < n; i++) {
      mArr[i % m] += times[i]; // 将任务分配给当前负载最小的机器（轮询分配）
    }

    return Arrays.stream(mArr).max().orElse(0); // 返回 mArr 数组中的最大值（最大负载）
  }
}

代码讲解：

1. 输入部分：
  • Scanner 类：
    • 使用 Scanner 类读取控制台输入。
    • 通过 sc.nextInt() 依次读取机器数量 m、任务数量 n 以及每个任务的执行时间。
  • times 数组：
    • 用于存储每个任务的执行时间。
    • 通过循环读取输入并存入 times 数组。
2. 数据处理部分：
  • 排序：
    • 使用 Arrays.sort(times) 对 times 数组进行升序排序，确保任务按执行时间从小到大分配。
  • 任务分配：
    • 定义数组 mArr，用于记录每台机器的总负载。
    • 使用循环将任务分配给当前负载最小的机器（通过 i % m 实现轮询分配）。
3. 输出部分：
  • Arrays.stream(mArr).max().orElse(0)：
    • 使用流操作计算 mArr 数组中的最大值（即所有机器中最大的负载）。
    • 如果数组为空，则返回默认值 0。
  • System.out.println：
    • 输出计算结果。

示例运行：

输入 1：
3 5
1 2 3 4 5
  • 输出：
    7
  • 解释：
    • m = 3（3 台机器），n = 5（5 个任务）。
    • 任务时间数组为 [1, 2, 3, 4, 5]。
    • 分配结果：
      • 机器 0：1 + 4 = 5
      • 机器 1：2 + 5 = 7
      • 机器 2：3 = 3
    • 最大负载为 7。
输入 2：
2 4
3 1 7 2
  • 输出：
    8
  • 解释：
    • m = 2（2 台机器），n = 4（4 个任务）。
    • 任务时间数组为 [1, 2, 3, 7]（排序后）。
    • 分配结果：
      • 机器 0：1 + 7 = 8
      • 机器 1：2 + 3 = 5
    • 最大负载为 8。

总结：

  • 该代码通过轮询分配的方式，将任务分配给负载最小的机器。
  • 使用 Arrays.sort 对任务执行时间进行排序，确保任务按时间从小到大分配。
  • 使用流操作计算数组中的最大值，简化代码逻辑。
  • 如果有其他问题，欢迎继续提问！

四、Python算法源码

以下是 Python 代码 的详细中文注释和讲解：

Python 代码

# 输入获取
m, n = map(int, input().split())  # 读取机器数量 m 和任务数量 n
times = list(map(int, input().split()))  # 读取每个任务的执行时间并存入列表 times

# 算法入口
def getResult():
    times.sort()  # 对任务执行时间列表进行升序排序

    mArr = [0] * m  # 定义列表 mArr，用于记录每台机器的总负载，初始值为 0

    for i in range(len(times)):  # 遍历任务执行时间列表
        mArr[i % m] += times[i]  # 将任务分配给当前负载最小的机器（轮询分配）

    return max(mArr)  # 返回 mArr 列表中的最大值（最大负载）

# 算法调用
print(getResult())  # 调用 getResult 方法计算结果并输出

代码讲解：

1. 输入部分：
  • input().split()：
    • 使用 input().split() 读取一行输入，并按空格分割成多个字符串。
  • map(int, ...)：
    • 将分割后的字符串转换为整数。
  • m, n：
    • 分别表示机器数量 m 和任务数量 n。
  • times 列表：
    • 用于存储每个任务的执行时间。
2. 数据处理部分：
  • 排序：
    • 使用 times.sort() 对 times 列表进行升序排序，确保任务按执行时间从小到大分配。
  • 任务分配：
    • 定义列表 mArr，用于记录每台机器的总负载，初始值为 0。
    • 使用循环将任务分配给当前负载最小的机器（通过 i % m 实现轮询分配）。
3. 输出部分：
  • max(mArr)：
    • 计算 mArr 列表中的最大值（即所有机器中最大的负载）。
  • print(getResult())：
    • 调用 getResult 方法计算结果并输出。

示例运行：

输入 1：
3 5
1 2 3 4 5
  • 输出：
    7
  • 解释：
    • m = 3（3 台机器），n = 5（5 个任务）。
    • 任务时间列表为 [1, 2, 3, 4, 5]。
    • 分配结果：
      • 机器 0：1 + 4 = 5
      • 机器 1：2 + 5 = 7
      • 机器 2：3 = 3
    • 最大负载为 7。
输入 2：
2 4
3 1 7 2
  • 输出：
    8
  • 解释：
    • m = 2（2 台机器），n = 4（4 个任务）。
    • 任务时间列表为 [1, 2, 3, 7]（排序后）。
    • 分配结果：
      • 机器 0：1 + 7 = 8
      • 机器 1：2 + 3 = 5
    • 最大负载为 8。

总结：

  • 该代码通过轮询分配的方式，将任务分配给负载最小的机器。
  • 使用 sort() 对任务执行时间进行排序，确保任务按时间从小到大分配。
  • 使用 max() 计算列表中的最大值，简化代码逻辑。
  • 如果有其他问题，欢迎继续提问！

五、C/C++算法源码：

以下是 C 语言代码 和 C++ 代码 的详细中文注释和讲解：

C 语言代码

#include <stdio.h>
#include <stdlib.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b)) // 定义宏 MAX，用于比较两个数的大小

// 比较函数，用于 qsort 排序
int cmp(const void* a, const void* b) {
    return (*(int*)a) - (*(int*)b); // 升序排序
}

int main() {
    int m, n;
    scanf("%d %d", &m, &n); // 读取机器数量 m 和任务数量 n

    int times[n]; // 定义数组 times，用于存储每个任务的执行时间
    for (int i = 0; i < n; i++) {
        scanf("%d", &times[i]); // 读取每个任务的执行时间并存入 times 数组
    }

    qsort(times, n, sizeof(int), cmp); // 对任务执行时间数组进行升序排序

    int* mArr = (int*)calloc(m, sizeof(int)); // 动态分配数组 mArr，用于记录每台机器的总负载，初始值为 0
    for (int i = 0; i < n; i++) {
        mArr[i % m] += times[i]; // 将任务分配给当前负载最小的机器（轮询分配）
    }

    int ans = mArr[0]; // 初始化最大负载为 mArr[0]
    for (int i = 1; i < m; i++) {
        ans = MAX(ans, mArr[i]); // 遍历 mArr，找到最大值
    }

    printf("%d\n", ans); // 输出最大负载

    free(mArr); // 释放动态分配的内存
    return 0;
}

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm> // 包含 sort 函数

using namespace std;

int main() {
    int m, n;
    cin >> m >> n; // 读取机器数量 m 和任务数量 n

    vector<int> times(n); // 定义 vector times，用于存储每个任务的执行时间
    for (int i = 0; i < n; i++) {
        cin >> times[i]; // 读取每个任务的执行时间并存入 times 数组
    }

    sort(times.begin(), times.end()); // 对任务执行时间数组进行升序排序

    vector<int> mArr(m, 0); // 定义 vector mArr，用于记录每台机器的总负载，初始值为 0
    for (int i = 0; i < n; i++) {
        mArr[i % m] += times[i]; // 将任务分配给当前负载最小的机器（轮询分配）
    }

    int ans = *max_element(mArr.begin(), mArr.end()); // 使用 max_element 找到 mArr 中的最大值
    cout << ans << endl; // 输出最大负载

    return 0;
}

代码讲解：

1. 输入部分：
  • C 语言：
    • 使用 scanf 读取机器数量 m 和任务数量 n。
    • 使用循环读取每个任务的执行时间并存入 times 数组。
  • C++：
    • 使用 cin 读取机器数量 m 和任务数量 n。
    • 使用 vector 存储任务执行时间，并通过循环读取输入。
2. 数据处理部分：
  • 排序：
    • C 语言：使用 qsort 对 times 数组进行升序排序。
    • C++：使用 sort 对 times 数组进行升序排序。
  • 任务分配：
    • C 语言：动态分配数组 mArr，用于记录每台机器的总负载，并通过循环将任务分配给当前负载最小的机器。
    • C++：使用 vector 存储每台机器的总负载，并通过循环将任务分配给当前负载最小的机器。
3. 输出部分：
  • C 语言：
    • 使用循环遍历 mArr，找到最大值并输出。
    • 使用 free 释放动态分配的内存。
  • C++：
    • 使用 max_element 找到 mArr 中的最大值并输出。

示例运行：

输入 1：
3 5
1 2 3 4 5
  • 输出：
    7
  • 解释：
    • m = 3（3 台机器），n = 5（5 个任务）。
    • 任务时间数组为 [1, 2, 3, 4, 5]。
    • 分配结果：
      • 机器 0：1 + 4 = 5
      • 机器 1：2 + 5 = 7
      • 机器 2：3 = 3
    • 最大负载为 7。
输入 2：
2 4
3 1 7 2
  • 输出：
    8
  • 解释：
    • m = 2（2 台机器），n = 4（4 个任务）。
    • 任务时间数组为 [1, 2, 3, 7]（排序后）。
    • 分配结果：
      • 机器 0：1 + 7 = 8
      • 机器 1：2 + 3 = 5
    • 最大负载为 8。

总结：

  • C 语言：
    • 使用 qsort 进行排序，动态分配内存，手动遍历数组找到最大值。
  • C++：
    • 使用 vector 和 sort 简化代码，使用 max_element 找到最大值。
  • 如果有其他问题，欢迎继续提问！

http://www.kler.cn/a/509758.html

相关文章：

  • Docker安装PostGreSQL docker安装PostGreSQL 完整详细教程
  • vscode 设置
  • 高性能、并发安全的 Go 嵌入式缓存库 如何使用？
  • 归并排序算法
  • R语言绘图
  • Android CustomTextField
  • 算法之 二叉树
  • 深入理解 SQL 中的 DATEDIFF 函数
  • Python基于Vue+Django网上商城的设计与实现【附源码】
  • “大数据+技校”：VR虚拟仿真实训室的发展前景
  • Windows图形界面(GUI)-QT-C/C++ - Qt Tree Widget详解与应用
  • 【机器学习实战入门】使用OpenCV进行性别和年龄检测
  • list转tensor很慢
  • SpringMVC——原理简介
  • openharmony标准系统芯片移植指导
  • 360AI平台资源可视化建设
  • Java开发提效秘籍：巧用Apache Commons IO工具库
  • 【力扣Hot 100】子串
  • 力扣动态规划-3【算法学习day.97】
  • React 中hooks之useLayoutEffect 用法总结以及与useEffect的区别
  • 多种vue前端框架介绍
  • 【项目推荐】CakeMu-RV：一个开放的 RISC-V 处理器模拟器学习项目
  • 服务器卡顿是否等同于遭受CC攻击？
  • Windows 下 Postgres 安装 TimescaleDB 插件
  • (RAG系列) FastGPT通过API调用工作流问答
  • ESP8266-01S的TCP/IP相关的AT指令