【2024年華為OD機試】 (B卷,100分)- 流水線（Java JS PythonC/C++）

在這里插入圖片描述

一、問題描述

題目描述

一個工廠有 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

輸出:

題目解析

簡單的邏輯題。解題思路如下：

題目說“總是優先執行處理時間最短的作業”，因此我們可以將 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)

計算每條流水線的時間總和，最大的那個就是題解。

詳細步驟

讀取輸入：
- 讀取流水線個數 m 和作業數 n。
- 讀取每個作業的處理時間 t1, t2, ..., tn。
排序：
- 將作業處理時間按升序排序。
初始化流水線：
- 創建一個數組 lines，長度為 m，初始化為 0，表示每條流水線的當前總耗時。
分配作業：
- 遍歷排序后的作業處理時間，依次將作業分配到當前總耗時最小的流水線中。
- 更新該流水線的總耗時。
輸出結果：
- 輸出所有流水線中最大總耗時。

用例解釋

用例 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(); // 讀取機器數量 mint n = sc.nextInt(); // 讀取任務數量 nint[] 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，用于記錄每臺機器的總負載，初始值為 0for 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 和任務數量 nint 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，用于記錄每臺機器的總負載，初始值為 0for (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 和任務數量 nvector<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，用于記錄每臺機器的總負載，初始值為 0for (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。