• 题目：

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都是 n ，再给你一个正整数 k 。你必须从 nums1 中选一个长度为 k 的 子序列 对应的下标。

对于选择的下标 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 是最大可能分数。

贪心思想：有约束，多维求最佳常用的一种方式。其中 A 可以是 除法/加法等，B 为单个元素（最大/最小值）

• 让 B 保持和题目最佳渐远的方式变化，比如题目要最大值，那么就降序
• 每次移除 A 中的最差结果，换一个更好的结果，也就是在 B 变差的情况下，A需要变好，才能让答案更优
• 比较获得最优解

class Solution {
        public long maxScore(int[] nums1, int[] nums2, int k) {
            int n = nums1.length;
            long ans = 0L;
            Integer[] sorts = new Integer[n];
            for(int i = 0; i < n; i++) sorts[i] = i;
            Arrays.sort(sorts,(a,b)->nums2[b]-nums2[a]); //根据num2的大小排序 sort记录num2从大到小的数的下标
            
            PriorityQueue<Integer> pq = new PriorityQueue<>(); //最小堆队列
            long sum = 0L;
            for(int i = 0; i < k-1; i++){ //k = 2则先存一个数到队列中，剩下一个数在下一个循环中加入进行比较再下一步处理
                sum += nums1[sorts[i]]; // 记录当前队列中数总和，即num1的和 （在num2最优的情况下添加同索引的num1）
                pq.offer(nums1[sorts[i]]); //放入队列
            }
            
            for(int i = k-1; i < n; i++){
                sum += nums1[sorts[i]]; //加上这次入队的数，
                pq.offer(nums1[sorts[i]]); //此时队列中几个数为同索引的num2的最优情况下的num1
                ans = Math.max(ans,nums2[sorts[i]]*sum); //sort就是num2从大到小的索引，所以nums2[sorts[i]]就是min（...）,计算后取最大
                sum -= pq.poll(); //踢出比较差的num1，因为在num2变差的情况，想取得最大值num1一定要变好
            }
            
            return ans;
        }
    }