老鼠和奶酪

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

问题描述

有两只老鼠和 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 是最高得分。

提示：

• 1 <= n == reward1.length == reward2.length <= 10^5
• 1 <= reward1[i], reward2[i] <= 1000
• 0 <= k <= n

思路分析

首先我们需要先理解一下题目的意思，题目会给我们两个数组reward1和reward2，reward1[i]表示第一只老鼠吃掉第 i 块奶酪可以得到的分数,reward2[i]表示第二只老鼠吃掉第 i 块奶酪可以得到的分数，我们需要计算第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。也就是说第一只老鼠要吃掉k块奶酪，剩下的奶酪应该都是第二只老鼠吃，要想要使得得到的分数最大,我们只需要保证第一只老鼠吃掉奶酪获得的分数与第二老鼠吃掉奶酪获得的分数分差最大即可，我们可以分为以下几个步骤来解题：

• 1、计算所有奶酪都给第二只老鼠吃掉得到的分数；

因为第一只老鼠只能吃k块奶酪，所以我们可以先计算将所有奶酪都给第二只老鼠吃掉的分数，后面在选出k块奶酪给第一只老鼠吃掉。

let res = 0;
for (let i = 0; i < reward2.length; i++) {
  res += reward2[i];
}

• 2、计算所有奶酪给第一只老鼠吃掉和第二只老鼠吃掉的分数差；

我们需要找出分数差最大的前k个奶酪来给第一只老鼠，我们可以先计算每一块奶酪给第一只老鼠吃掉和第二只老鼠吃掉的分数差。

const reward = [];
for (let i = 0; i < reward1.length; i++) {
  reward[i] = reward1[i] - reward2[i];
}

• 3、将分数差最大的前 k 个奶酪给第一只老鼠吃掉

上一步已经计算出了每一块奶酪给两只老鼠吃掉的分数差，我们只需要对其进行排序，找出分数差最大的前k个即可。

reward.sort((a, b) => b - a);
for (let i = 0; i < k; i++) res += reward[i];

AC 代码

完整 AC 代码如下：

/**
 * @param {number[]} reward1
 * @param {number[]} reward2
 * @param {number} k
 * @return {number}
 */
var miceAndCheese = function (reward1, reward2, k) {
  const reward = [];
  let res = 0;
  for (let i = 0; i < reward1.length; i++) {
    reward[i] = reward1[i] - reward2[i];
    res += reward2[i];
  }
  reward.sort((a, b) => b - a);
  for (let i = 0; i < k; i++) res += reward[i];
  return res;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。