老鼠和奶酪【LC2611】

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

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

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

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

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

套路题，也不大容易想到

• 思路

  假设所有的奶酪都没第二只老鼠吃了，那么此时得分为$sum(reward2[i])$，在此基础上我们需要挑选$k$块奶酪给第一只老鼠吃，那么此时分数的变化量为
  $$diff=\sum _{i=0}^{k}reward1[i]-reward2[i]$$
  我们需要尽可能使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)$