Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 2542. Maximum Subsequence Score

---

參考資訊：
https://algo.monster/liteproblems/2542
https://www.cnblogs.com/cnoodle/p/17549555.html
https://www.geeksforgeeks.org/c/c-program-to-implement-priority-queue/

題目：


解答：

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<pair<int, int>> s;

        for (int i = 0; i < nums1.size(); i++) {
            s.emplace_back(pair<int, int>(nums2[i], nums1[i]));
        }
        sort(s.begin(), s.end());

        long long r = 0;
        long long sum = 0;
        priority_queue<int, vector<int>, greater<int>> q;

        for (auto it = s.rbegin(); it != s.rend(); it++) {
            int n2 = it->first;
            int n1 = it->second;

            sum += n1;
            q.push(n1);

            if (q.size() == k) {
                r = max(r, sum * n2);

                sum -= q.top();
                q.pop();
            }
        }

        return r;
    }
};