LeetCode 2542. 最大子序列的分数（贪心、小顶堆）

2542. 最大子序列的分数

思路：先对nums2按降序排列，然后遍历nums2的最小值，同时在区间[0,i]中选中k个最大的nums1即可。然后找出最大的ans

class Solution {
public:
    typedef pair<int,int> PII;
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
    	//将nums1和nums2结合起来，按nums2的降序排列
        vector<PII> v;
        for(int i=0;i<nums1.size();i++){
            v.push_back({nums2[i],nums1[i]});
        }
        sort(v.rbegin(),v.rend());
        //记录在[0,i]区间最大的k个nums1的和
        long long sum=0;
        //小顶堆记录选中的k个nums1
        priority_queue<int,vector<int>,greater<int>> qu;
        //记录最大值
        long long ans=0;
        for(int i=0;i<v.size();i++){
        	//数量不够k个，就得都选
            if(i<k){
                qu.push(v[i].second);
                sum+=v[i].second;
            }else{
            	//因为nums2是降序的，所以我们只需要维护最大的k个nums1的和
                if(qu.top()<v[i].second){
                    sum=sum-qu.top()+v[i].second;
                    qu.pop();
                    qu.push(v[i].second);
                }
                
            }
            //当选中的数超过k个值时，就开始更新ans
            if(i>=k-1){
                ans=max(ans,sum*v[i].first);
            }
        }
        return ans;
    }
};