題目描述:
有 n 個工程師,每人有 speed[i] 和 efficiency[i]。從中選最多 k 個工程師組成團隊。團隊表現定義為「所選工程師的速度總和 * 所選工程師中最低效率」。回傳最大表現值(取模 10^9+7)。
解題思路: 關鍵洞察:「最低效率」是瓶頸。我們可以枚舉每個工程師作為效率最低的那位。
speedSum * currentEfficiency,更新全局最大值。按效率遞減遍歷保證了每一步的「最低效率」就是當前工程師的效率值。
時間複雜度: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,但狀態定義困難(需記錄選了多少人及速度總和),且不如貪心 + 堆的方法直觀和高效。