---
# System prepended metadata

title: 2542. Maximum Subsequence Score
tags: [Heap / Priority Queue]

---

思考:
1.hard

```c++=
#define pii pair<int,int>
class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        // 定義兩個優先隊列，一個是大根堆（最大堆），一個是小根堆（最小堆）
        // 大根堆用於選擇最大的元素，小根堆用於選擇最小的元素
        priority_queue<pii> maxHeap;
        priority_queue<pii,vector<pii>,greater<pii>> minHeap;

        long long ans=INT_MIN; // 初始化答案為最小值
        long long score=0; // 用於計算當前乘積和
        long long sum=0; // 用於紀錄目前所選元素的總和
        
        // 將 nums1 的元素依次放入大根堆
        for(int i=0;i<nums1.size();i++) {
            maxHeap.push({nums1[i],i});
        }
        
        // 選擇最大的 k 個元素，並將對應的 nums2 元素放入小根堆
        while(!maxHeap.empty() && k>0) {
            pii top = maxHeap.top();
            sum+=top.first; // 將元素值加入目前總和
            minHeap.push({nums2[top.second],top.second}); // 放入小根堆
            maxHeap.pop();
            k--;
        }

        // 取得小根堆中最小的元素，作為乘積的係數（最小元素）
        int minmul=minHeap.top().first;

        // 計算目前的乘積和
        score=sum*minmul;
        ans=max(ans,score); // 更新答案
         
        while(!maxHeap.empty()) {
            // 取得小根堆中最小的元素，作為當前限制乘積的係數
            pii mintop=minHeap.top();
            // 減去對應的 nums1 元素
            sum-=nums1[mintop.second];
            minHeap.pop();

            // 取得大根堆中最大的元素，作為下一輪要加入的元素
            pii maxtop=maxHeap.top();
            sum+=maxtop.first; // 加入總和
            minHeap.push({nums2[maxtop.second],maxtop.second}); // 放入小根堆
            maxHeap.pop();

            // 取得小根堆中最小的元素，作為乘積的係數
            minmul=minHeap.top().first;
            // 更新乘積和和答案
            score=sum*minmul;
            ans=max(ans,score);
        }
        return ans; // 返回最大的乘積和
    }
};

```