力扣2542.最大子序列的分数

本文主要是介绍力扣2542.最大子序列的分数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣2542.最大子序列的分数

• 转换 + 最小堆

  • 因为要求找nums2中k数区间的最小值，所以考虑按照nums2从大到小排序
  • 这样枚举nums2中[k-1,n]的数都可以作为最小值

•   class Solution {public:long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {int n = nums1.size();vector<int> ids(n);iota(ids.begin(),ids.end(),0);//下标按照nums2的大小排序ranges::sort(ids,[&](int i,int j){return nums2[i] > nums2[j];});//放nums1的数priority_queue<int,vector<int>,greater<>> pq;long long sum = 0;//初始化求前k个数的for(int i=0;i<k;i++){sum += nums1[ids[i]];pq.push(nums1[ids[i]]);}long long ans = sum * nums2[ids[k-1]];//枚举nums2[ids[i]]作为最小值for(int i=k;i<n;i++){//新的数int x = nums1[ids[i]];//比最小数大，更优if(x > pq.top()){sum += x - pq.top();pq.pop();pq.push(x);ans = max(ans,sum * nums2[ids[i]]);}}return ans;}};
  

这篇关于力扣2542.最大子序列的分数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---