[Leetcode] 2542. Maximum Subsequence Score

1. 문제링크

https://leetcode.com/problems/maximum-subsequence-score/

Maximum Subsequence Score - LeetCode

- nums1 : sum nums

- nums2 : mul nums (여기서 최소값만 사용)

 

 

2. 키 포인트

1) 배열은 nums2기준으로 정렬한다

2) priority_queue를 사용한다

    pq사이즈가 k가 될 때, 숫자의 합과 최소 min으로 곱한 값 중에 최댓값을 업데이트해준다

    pq사이즈는 k가 넘으면 pop해준다

 

 

3. solution

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<pair<int,int>>v;
        int size = nums1.size();
        for(int i = 0; i < size; i++){
            v.push_back({nums2[i], nums1[i]});
        }
        sort(v.begin(), v.end());
        priority_queue<int, vector<int>, greater<int>> pq;
        long long ans = 0, sum = 0;
        for(int i = size-1; i >= 0; i--){
            if(pq.size() >= k){
                sum -= pq.top();
                pq.pop();                
            }
            sum += v[i].second;
            pq.push(v[i].second);
            if(pq.size() == k)
                ans = max(ans, v[i].first * sum);
        }
        return ans;
    }
};