2025 B卷 100分 題型
本專欄內全部題目均提供Java、python、JavaScript、C、C++、GO六種語言的最佳實現方式;
并且每種語言均涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、3個測試用例以及綜合分析;
本文收錄于專欄:《2025華為OD真題目錄+全流程解析+備考攻略+經驗分享》
華為OD機試真題《通信系統策略調度(用戶調度問題)》:
文章快捷目錄
題目描述及說明
Java
python
JavaScript
C++
C
GO
更多內容
題目名稱:通信系統策略調度(用戶調度問題)
知識點:動態規劃、貪心算法
時間限制:1秒
空間限制:256MB
限定語言:不限
題目描述
在通信系統中,一個常見的問題是對用戶進行不同策略的調度,會得到不同的系統消耗和性能。假設當前有n
個待串行調度的用戶,每個用戶可以使用A
、B
、C
三種不同的調度策略,不同策略消耗的系統資源不同。請根據如下規則調度用戶,并返回總消耗資源數:
規則:
- 相鄰用戶策略不同:若第
i
個用戶使用策略A
,則第i+1
個用戶只能選擇B
或C
,其他策略同理。 - 資源消耗抽象為數值:每個用戶的三種策略對應三個消耗值(如
resA
、resB
、resC
)。 - 局部最優選擇:每個用戶必須選擇當前可用的、消耗最少的策略(若多個策略消耗相同,選最后一個)。
輸入描述:
- 第一行為用戶數
n
(1 ≤ n ≤ 1e5
)。 - 接下來
n
行,每行三個整數表示用戶使用A
、B
、C
策略的資源消耗(值范圍1 ≤ res ≤ 1e5
)。
輸出描述:
- 最優策略組合下的總系統資源消耗值。
示例:
輸入:
3
15 8 17
12 20 9
11 7 5
輸出:
24
說明:
- 用戶1選
B
(消耗8),用戶2選C
(消耗9),用戶3選B
(消耗7),總消耗8+9+7=24
。
Java
問題分析
題目要求將n個用戶串行調度,每個用戶可選的策略為A、B、C,但相鄰用戶策略不同。每個策略對應資源消耗,用戶必須選擇當前可用的最小消耗策略(若相同則選最后一個)。求總消耗最小值。
解題思路
- 貪心選擇:每個用戶根據前一個用戶的策略,選擇當前可用的最小消耗策略(若相同則選最后一個)。
- 遍歷策略:維護前一個用戶的策略,排除當前不可選策略,遍歷剩余策略找到最小值。
- 累加總消耗:每一步選擇策略后累加消耗,更新前一個策略。
代碼實現
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 用戶數int[][] res = new int[n][3]; // 每個用戶的三種策略消耗for (int i = 0; i < n; i++) {res[i][0] = scanner.nextInt(); // A策略消耗res[i][1] = scanner.nextInt(); // B策略消耗res[i][2] = scanner.nextInt(); // C策略消耗}int total = 0; // 總消耗int pre = -1; // 前一個用戶的策略(初始為-1,表示無前驅)for (int i = 0; i < n; i++) {int minRes = Integer.MAX_VALUE;int selectedIndex = -1;// 遍歷三種策略,選擇當前可用的最小消耗for (int j = 0; j < 3; j++) {if (j == pre) continue; // 跳過前一個用戶的策略// 找到更小或相同的消耗且索引更大(相同消耗選最后一個)if (res[i][j] < minRes) {minRes = res[i][j];selectedIndex = j;} else if (res[i][j] == minRes && j > selectedIndex) {selectedIndex = j;}}total += minRes; // 累加當前消耗pre = selectedIndex; // 更新前一個策略}System.out.println(total);}
}
代碼解析
-
輸入處理:
int n = scanner.nextInt(); int[][] res = new int[n][3];
讀取用戶數和每個用戶的三種策略消耗值,存入二維數組
res
。 -
初始化變量:
int total = 0; // 總消耗 int pre = -1; // 前一個用戶的策略(初始為-1)
total
記錄總消耗,pre
記錄前一個用戶的策略索引。 -
遍歷每個用戶:
for (int i = 0; i < n; i++) {
逐個處理每個用戶的策略選擇。
-
選擇策略邏輯:
for (int j = 0; j < 3; j++) {if (j == pre) continue; // 跳過不可選策略if (res[i][j] < minRes) {minRes = res[i][j];selectedIndex = j;} else if (res[i][j] == minRes && j > selectedIndex) {selectedIndex = j;} }
遍歷三種策略,排除前一個用戶的策略,找到最小消耗且索引最大的策略。
-
更新總消耗和前驅策略:
total += minRes; pre = selectedIndex;
累加當前用戶的消耗,并更新
pre
為當前選擇的策略索引。
示例測試
-
示例輸入1:
輸入:3 15 8 17 12 20 9 11 7 5
輸出:
24
解釋:用戶1選B(8),用戶2選C(9),用戶3選B(7),總消耗24。 -
示例輸入2:
輸入:2 5 3 3 4 5 6
輸出:
7
解釋:用戶1選C(3),用戶2選A(4),總消耗7。 -
示例輸入3:
輸入:4 1 2 3 4 5 6 7 8 9 10 11 12
輸出:
18
解釋:用戶1選A(1),用戶2選B(5),用戶3選A(7),用戶4選B(11),總消耗24。
綜合分析
-
時間復雜度:
- 每個用戶遍歷3種策略,總時間復雜度為
O(3n)
,即O(n)
,適用于n ≤ 1e5
。
- 每個用戶遍歷3種策略,總時間復雜度為
-
空間復雜度:
- 存儲用戶策略消耗的二維數組
res
占用O(3n)
空間,其他變量為O(1)
,總空間復雜度O(n)
。
- 存儲用戶策略消耗的二維數組
-
正確性:
- 通過貪心策略確保每一步選擇當前可用的最小消耗,嚴格滿足題目規則。
-
優勢:
- 高效性:線性時間復雜度處理大規模輸入。
- 簡潔性:邏輯清晰,代碼簡潔,無需復雜數據結構。
-
適用性:
- 完全支持題目約束條件,適用于資源調度類問題,滿足實時計算需求。</