2542. Maximum Subsequence Score

解題思路

解法參考其他大神，沒指望自己能想出來，只是順手紀錄幾個部分。

pair sorting 是預設 sort first element。

以及

sort(rbegin(), rend()) 是由大排序到小。

程式碼

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<pair<int, int>> v;
        for(int i=0; i<nums1.size(); i++)
            v.push_back({nums2[i], nums1[i]});
        sort(rbegin(v), rend(v));

        long long ans = 0, currentSum = 0;
        priority_queue<int, vector<int>, greater<int>> pq;
        for(auto [second, first] : v)
        {
            pq.emplace(first);
            currentSum += first;

            if(pq.size() > k)
            {
                currentSum -= pq.top();
                pq.pop();
            }
            if(pq.size() == k)
                ans = max(ans, currentSum * second);
        }
        return ans;
    }
};