Description

You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.

For chosen indices i0, i1, ..., ik - 1, your score is defined as:

• The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.
• It can defined simply as: (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]).

Return the maximum possible score.

A subsequence of indices of an array is a set that can be derived from the set {0, 1, ..., n-1} by deleting some or no elements.

---

두 개의 0-인덱스 정수 배열 nums1과 nums2가 주어지며, 두 배열의 길이는 n이고 양의 정수 k가 주어집니다. 여러분은 nums1에서 길이가 k인 부분 수열(subsequence)의 인덱스를 선택해야 합니다.

선택된 인덱스 i0, i1, ..., ik - 1에 대해, 여러분의 점수는 다음과 같이 정의됩니다:

• nums1에서 선택된 요소들의 합과 nums2에서 선택된 요소들의 최솟값을 곱한 값입니다.
• 간단하게 정의하자면, (nums1[i0] + nums1[i1] + ... + nums1[ik - 1]) * min(nums2[i0], nums2[i1], ..., nums2[ik - 1]).

가능한 최대 점수를 반환하세요.

배열의 인덱스 부분 수열은 집합 {0, 1, ..., n-1}에서 일부 또는 전혀 원소를 삭제하여 얻을 수 있는 집합입니다.

예제 1:

입력: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
출력: 12
설명:
네 가지 가능한 부분 수열 점수는 다음과 같습니다:

• 인덱스 0, 1, 2를 선택할 때 점수 = (1+3+3) * min(2,1,3) = 7.
• 인덱스 0, 1, 3을 선택할 때 점수 = (1+3+2) * min(2,1,4) = 6.
• 인덱스 0, 2, 3을 선택할 때 점수 = (1+3+2) * min(2,3,4) = 12.
• 인덱스 1, 2, 3을 선택할 때 점수 = (3+3+2) * min(1,3,4) = 8.
  따라서, 최대 점수인 12를 반환합니다.

예제 2:

입력: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
출력: 30
설명:
인덱스 2를 선택하는 것이 최적입니다: nums1[2] nums2[2] = 3 10 = 30은 가능한 최대 점수입니다.

제약 조건:

• n == nums1.length == nums2.length
• 1 <= n <= 105
• 0 <= nums1[i], nums2[j] <= 105
• 1 <= k <= n

Solution

class Solution {
    public long maxScore(int[] speed, int[] efficiency, int k) {
        int n = speed.length;
        int[][] ess = new int[n][2];
        for (int i = 0; i < n; ++i){
            ess[i][0] = efficiency[i];
            ess[i][1] = speed[i];
        }
        
        Arrays.sort(ess, (a, b) -> -Integer.compare(a[0], b[0]));

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        long score = 0, total = 0;
        for (int[] es : ess) {
            pq.add(es[1]);
            total += es[1];
            if (pq.size() > k) total -= pq.poll();
            if (pq.size() == k) score = Math.max(score, (total * es[0]));
        }
        return score;
    }
}