首页 > 编程语言 >【2024年华为OD机试】 (B卷,100分)- 流水线（Java & JS & Python&C/C++）

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

时间：2025-01-18 09:59:37浏览次数：3  
标签：负载 机器 数组 Python OD times int mArr Java

在这里插入图片描述

一、问题描述

题目描述

一个工厂有 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 找到最大值。
  • 如果有其他问题，欢迎继续提问！

标签：负载,机器,数组,Python,OD,times,int,mArr,Java
From： https://blog.csdn.net/m0_63168877/article/details/145101092

相关文章

  • 股票API接口使用python、JAVA等多种语言实例代码演示免费获取实时数据、历史数据、CDM
    ​最新整理的股票API接口，下方所有接口链接均可直接点击验证，查看返回的数据。沪深两市股票列表股票API接口链接（可点击验证）：https://api.mairui.club/hslt/list/LICENCE-66D8-9F96-0C7F0FBCD073【实时数据接口】沪深两市实时交易数据接口股票API接口链接（可点击验证）：https:......
  • Python 进阶 - 多线程(一)
    Python进阶-多线程相关概念解释器GILthreading方法属性threading.enumerate()threading.active_count()threading.current_thread()threading.get_ident()threading.main_thread()threading.stack_size([size])threading.get_native_id()threading.TIMEOUT_MAX线程......
  • leetcode——令牌放置（java）
    你的初始能量为power，初始分数为0，只有一包令牌以整数数组tokens给出。其中tokens[i]是第i个令牌的值（下标从0开始）。你的目标是通过有策略地使用这些令牌以最大化总分数。在一次行动中，你可以用两种方式中的一种来使用一个未被使用的令牌（但不是对同一个令牌使......
  • SpringCloud+Vue+Python人工智能（fastAPI,机器学习,深度学习）前后端架构各功能实现思路
    随着公司业务的增加，公司需要一个java+python人工智能相互配合架构，正常网站业务用java来做，而ai，例如电价预测等回归任务，以及大模型预测全网负荷，新能源出力等任务，使用python通过fastapi暴露接口来做，那么就需要springcloud架构注册发现。前端统一使用Vue进行效果的展示因此本......
  • node.js毕设工商学院宿舍管理系统论文+程序
    本系统（程序+源码+数据库+调试部署+开发环境）带文档lw万字以上，文末可获取源码系统程序文件列表开题报告内容选题背景关于高校宿舍管理系统的研究，现有研究主要以满足基本的住宿安排和人员信息管理为主。在国外，一些先进的高校宿舍管理系统已实现高度智能化，涵盖从入住到离校的......
  • 【华为OD技术面试手撕真题】- C++手撕技术面试八股文（3）
    文章目录一、常见的STL容器有哪些？1、序列容器2、关联容器3、无序关联容器4、容器适配器二、STL中map和set的原理1、基本数据结构（红黑树）2、map3、set4、特点和应用三、深拷贝和浅拷贝的区别1、浅拷贝2、深拷贝四、什么情况下会调用拷贝构造函......
  • 【华为OD技术面试手撕真题】- C++手撕技术面试八股文（2）
    文章目录一、struct结构体和共同体union共同体的区别1、内存分配2、成员访问3、使用场景4、定义方式5、总结二、堆和栈的区别1、内存分配方式2、生命周期3、大小限制4、内存访问速度5、数据存储6、多线程的影响三、什么是内存泄漏？面对内存泄漏和......
  • Python图形用户界面（GUI）库
    Python图形用户界面（GUI）库是用于创建图形用户界面的工具集，它们允许开发者使用Python语言来构建具有图形元素的用户界面。以下是一些常用的PythonGUI库：1.Tkinter•简介：Tkinter是Python的标准GUI库，它提供了创建窗口、按钮、文本框和其他GUI组件的工具。由于它是Python安装包......
  • java集合
    集合想一下，目前为止，我们学过哪些可以存储元素的容器：1、数组，查询快，增删慢。既可以存储基本数据类型的元素，又可以存储引用数据类型的元素对于同一个数组而言，元素类型都是一样长度一旦创建旧固定了，不能改变长度。2、StringBuffer长度可以随着添加的字符个数而改变StringBuffe......
  • java常用类
    java常用类Api概述API(ApplicationProgrammingInterface)应用程序编程接口编写一个机器人程序去控制机器人踢足球，程序就需要向机器人发出向前跑、向后跑、射门、抢球等各种命令，没有编过程序的人很难想象这样的程序如何编写。但是对于有经验的开发人员来说，知道机器人厂商一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99