HardRating 2091

1383. Maximum Performance of a Team

arraygreedysortingheap-priority-queue

解題說明

Maximum Performance of a Team

題目描述：有 n 個工程師，每人有 speed[i] 和 efficiency[i]。從中選最多 k 個工程師組成團隊。團隊表現定義為「所選工程師的速度總和 * 所選工程師中最低效率」。回傳最大表現值（取模 10^9+7）。

解題思路：關鍵洞察：「最低效率」是瓶頸。我們可以枚舉每個工程師作為效率最低的那位。

將所有工程師按效率從高到低排序。
依序遍歷，每個工程師加入候選集合。當前工程師的效率就是團隊的最低效率。
為了最大化速度總和，使用最小堆維護當前速度最大的 k 個工程師。若堆大小超過 k，彈出速度最小的。
每步計算 speedSum * currentEfficiency，更新全局最大值。

按效率遞減遍歷保證了每一步的「最低效率」就是當前工程師的效率值。

C++ 解法

複雜度分析

時間複雜度：O(n log n) — 排序 O(n log n)，每個工程師的堆操作 O(log k)，總計 O(n log n + n log k) = O(n log n)。

空間複雜度：O(n + k) — 索引陣列 O(n)，堆大小最多 k。

虛擬碼

1. Create index array [0, 1, ..., n-1]
2. Sort indices by efficiency in descending order
3. Initialize minHeap (by speed), speedSum = 0, ans = 0
4. For each index i in sorted order:
   a. Push speed[i] into minHeap, add to speedSum
   b. If heap size > k:
      - speedSum -= minHeap.top()
      - Pop minHeap
   c. ans = max(ans, speedSum * efficiency[i])
5. Return ans % (10^9 + 7)

其他解法

暴力枚舉 O(C(n,k) * k)：列舉所有大小最多 k 的子集，計算每個子集的表現。指數級時間，僅適合 n 極小的情況。

DP 方法：排序後使用 DP，但狀態定義困難（需記錄選了多少人及速度總和），且不如貪心 + 堆的方法直觀和高效。

延伸思考

若團隊表現定義改為「速度總和 * 最高效率」，演算法需要如何調整？
若必須恰好選 k 個工程師（不能少於 k），結果會有什麼不同？
若要回傳具體選了哪些工程師（而非只回傳最大值），如何記錄？

Maximum Performance of a Team — CaffeCode