【每日一题Day230】LC2611老鼠和奶酪 | 排序+贪心

老鼠和奶酪【LC2611】

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。

下标为 i 处的奶酪被吃掉的得分为：

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

给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。

请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。

套路题，也不大容易想到

• 思路
  假设所有的奶酪都没第二只老鼠吃了，那么此时得分为sum(reward2[i])，在此基础上我们需要挑选k kk块奶酪给第一只老鼠吃，那么此时分数的变化量为

我们需要尽可能使diff大【局部最优】，以获得最大得分【全局最优】，因此可以将数组reward1[i]-reward2[i]排序，累加最大的k个变化量至sum，即为最终结果

实现

class Solution {
    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        int res = 0, n = reward1.length;
        for (int i = 0; i < n; i++){
            res += reward2[i];
            reward1[i] -= reward2[i];
        }
        Arrays.sort(reward1);
        for (int i = 0; i < k; i++){
            res += reward1[n - 1 - i];
        }
        return res;
    }
}

复杂度

• 时间复杂度：O ( n log ⁡n )
• 空间复杂度：O ( log ⁡n )