题目描述

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

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

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

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

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

示例 1：

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

示例 2：

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

分析

假设所有的奶酪都被第二只老鼠吃掉，记录下此时得分res。若第i块奶酪被第一只老鼠吃掉，得分变化为reward1[i]-reward2[i]，建立数组reward，其中reward[i]=rewar1d[i]-reward2[i]，并对reward数组排序，res加上reward后k个元素（也就是第一只老鼠吃k块的最大值变化）即为最终结果。

代码

class Solution {

  public int miceAndCheese(int[] reward1, int[] reward2, int k) {

    int ans = 0;

    int n = reward1.length;

    int[] diffs = new int[n];

    for (int i = 0; i < n; i++) {

      ans += reward2[i];

      diffs[i] = reward1[i] - reward2[i];

    }

    Arrays.sort(diffs);

    for (int i = 1; i <= k; i++) {

      ans += diffs[n - i];

    }

    return ans;

  }

}