2611. 老鼠和奶酪

做一棵简单生活着的树,用自己的美丽去点击世界的美丽;用自己的浓荫,梳
理世间的清凉;用自己的快乐,点缀时光的流逝;用自己的爱,为心爱的人增添快乐。

LC每日一题，参考2611. 老鼠和奶酪。

题目

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。
下标为 i 处的奶酪被吃掉的得分为：

• 如果第一只老鼠吃掉，则得分为 reward1[i] 。
• 如果第二只老鼠吃掉，则得分为 reward2[i] 。

给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。
请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。

输入：reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
输出：15
解释：这个例子中，第一只老鼠吃掉第 2 和 3 块奶酪（下标从 0 开始），第二只老鼠吃掉第 0 和 1 块奶酪。
总得分为 4 + 4 + 3 + 4 = 15 。
15 是最高得分。
输入：reward1 = [1,1], reward2 = [1,1], k = 2
输出：2
解释：这个例子中，第一只老鼠吃掉第 0 和 1 块奶酪（下标从 0 开始），第二只老鼠不吃任何奶酪。
总得分为 1 + 1 = 2 。
2 是最高得分。

解题思路

• 排序+贪心：要想得到最高得分必须全部吃完,且优先吃两个得分差值最大的。

排序+贪心

class Solution {
    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        //考虑排序+贪心 最大得分所以肯定要全部吃完,第二只吃n-k个
        int n = reward1.length;
        Integer[] sort = new Integer[n];
        for(int i = 0; i < n; i++) sort[i] = i; //对下标排序
        Arrays.sort(sort,(a,b)->Math.abs(reward1[b]-reward2[b])-
            Math.abs(reward1[a]-reward2[a]));
        int i = k,j = n - k,id = 0,ans = 0;
        while(id < n) {
            if(i > 0 && j > 0) {//两个都可以吃
                if(reward1[sort[id]] > reward2[sort[id]]) i -= 1;
                else j -= 1;
                ans += Math.max(reward1[sort[id]],reward2[sort[id]]);
                id += 1;
            }else if(i > 0) {
                i -= 1;
                ans += reward1[sort[id++]];
            }else {
                j -= 1;
                ans += reward2[sort[id++]];
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(nlogn)，n为数组长度,排序时间nlogn,计算最大值时间n。
• 空间复杂度：O(n)，排序数组n,排序使用空间logn。