2542. Maximum Subsequence Score

📘 題目敘述

給你兩個長度相同、0-indexed 的整數陣列 nums1 與 nums2，以及一個正整數 k。你必須從索引集合 {0,1,...,n-1} 中選出一個長度為 k 的 subsequence（只要選索引，不要求連續）。

假設選到的索引是 i0, i1, ..., i(k-1)，分數定義為：

分數 =（選到的 nums1 總和）×（選到的 nums2 最小值）
也就是 (nums1[i0] + ... + nums1[i(k-1)]) * min(nums2[i0], ..., nums2[i(k-1)])

請回傳可以得到的最大分數。

條件限制

n == nums1.length == nums2.length
1 <= n <= 10^5
0 <= nums1[i], nums2[i] <= 10^5
1 <= k <= n

🧠 解題思路

這題的關鍵是：分數裡面有一個 min(nums2)，很難直接同時最大化「總和」與「最小值」。

我用的想法是「先決定最小值是誰」。

如果我們假設答案選出的 k 個索引中，min(nums2) 的值剛好等於某個值 a，那代表被選到的所有元素都必須滿足 nums2 >= a，而且至少要包含一個 nums2 == a 的元素。

因此我把 (nums2[i], nums1[i]) 配對起來，並且按照 nums2 由大到小排序。當我掃描到某個 pair (a, b) 時，意思是：

目前掃過的所有元素，其 nums2 都 >= a
如果我現在決定 min(nums2) = a，那我只能從「目前掃過的這些元素」裡面挑 k 個
在這個前提下，我要最大化分數 sum(nums1選到的k個) * a
因為 a 已經固定，所以只要讓 sum(nums1) 最大就好

所以在掃描過程中，我維護「目前看過的元素裡，最大的 k 個 nums1 的總和」。做法是用一個 min-heap：

heap 裡放我目前選的 nums1 值
讓 heap 大小最多維持 k
每次加入一個新的 nums1，如果超過 k，就把最小的那個踢掉
這樣 heap 裡永遠是「目前為止最大的 k 個 nums1」
當 heap 大小剛好是 k，就可以用 sum * a 更新答案

這就是為什麼我先排序 nums2，再用 priority_queue 去維護 nums1。

所有變數

n：陣列長度
v：vector<pair<int,int>>，存 (nums2[i], nums1[i])
q：priority_queue<int, vector<int>, greater<int>>，min-heap，用來維護目前挑選的 k 個 nums1（保留最大的 k 個，所以要踢最小的）
sum：目前 heap 裡所有 nums1 的總和（用 long long 避免溢位）
ans：答案最大值（用 long long）

🪜 主要流程步驟

1. 存pair並排序

把每個位置 i 變成 pair (nums2[i], nums1[i]) 存進 v
將 v 依照 nums2 由大到小排序我是先 sort（升序）再 reverse，最後效果是降序

2. 逐個掃描，維護「最大的 k 個 nums1」

對 v 的每個 (a, b)（a=nums2, b=nums1）：
把 b 放進 min-heap q
sum += b
如果 q.size() > k：
- 代表多放了一個，需要把最小的 nums1 移除
- sum -= q.top()，然後 q.pop()

3. 用當前 a 當作 min(nums2) 嘗試更新答案

當 q.size() == k，代表在「nums2 >= a」這個範圍內，我已經維持住最大的 k 個 nums1
此時如果 min(nums2) 就是 a，那分數是 sum * a
用 ans = max(ans, sum * a) 更新

4. 回傳答案

掃描結束後回傳 ans

💻 程式碼實作

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size();
        vector<pair<int, int>> v;
        for (int i = 0; i < n; i++) {
            v.push_back({nums2[i], nums1[i]});
        }
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
        priority_queue<int, vector<int>, greater<int>> q;
        long long sum = 0, ans = 0;
        for (auto& [a, b] : v) {
            q.push(b);
            sum += b;
            if (q.size() > k) {
                sum -= q.top();
                q.pop();
            }
            if (q.size() == k) {
                ans = max(ans, sum * a);
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/maximum-subsequence-score/