题目描述:
主要思路:
这是一个堆的题目,首先将2里边的下标按照数值递减的顺序进行重新排列。依次遍历2的下标同时加上1的数值,堆里边存储1的大小。
class Solution {
public:long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {int n=nums1.size();vector<int> idx(n);iota(idx.begin(),idx.end(),0);priority_queue<int,vector<int>,greater<int>> q;sort(idx.begin(),idx.end(),[&](int x,int y){return nums2[x]>nums2[y];});long long sum=0,ans=0;for(auto i:idx){if(q.size()>=k){sum-=q.top();q.pop();}sum+=nums1[i];q.push(nums1[i]);if(q.size()==k)ans=max(ans,sum*nums2[i]);}return ans;}
};