老鼠和奶酪

难度: Medium

有两只老鼠和 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⁵
1 <= reward1[i], reward2[i] <= 1000
0 <= k <= n

Submission

运行时间: 80 ms

内存: 27.7 MB

class Solution:
    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:
        for i,j in enumerate(reward2):
            reward1[i]-=j
        reward1.sort(reverse=True)
        return sum(reward2)+sum(reward1[:k])

Explain

题解的思路是通过计算每块奶酪被第一只老鼠吃与第二只老鼠吃的得分差值来决定分配。首先，将每块奶酪的得分差值计算出来，并与原有第二只老鼠的得分数组结合。差值大的奶酪优先被第一只老鼠吃，因为这样可以最大化总得分。最后，根据差值排序，取出差值最大的前k块奶酪的差值，再加上所有奶酪的第二只老鼠的得分，得到最终的最大得分。

时间复杂度: O(n log n)

空间复杂度: O(log n)

# 注释版代码

class Solution:
    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:
        for i, j in enumerate(reward2):
            reward1[i] -= j  # 计算得分差值，并直接在reward1中更新以节省空间
        reward1.sort(reverse=True)  # 对差值进行降序排序，以便优先考虑得分差最大的奶酪
        return sum(reward2) + sum(reward1[:k])  # 返回第二只老鼠的总得分加上第一只老鼠的最高k个得分差

Explore

使用得分差值是为了衡量选择某块奶酪对总得分影响的大小。当我们比较得分差值而非单独得分，实际上是在评估将该奶酪从第二只老鼠转给第一只老鼠时的得分变化。这种方法帮助我们优先考虑那些转移后能最大化得分增益的奶酪，即那些差值最大的奶酪。如果只比较两只老鼠的具体得分，我们无法直接得知转移奶酪的得分效益，因此使用得分差值能更有效地做出决策。

在大多数情况下，这种基于得分差值的方法能够有效地增加总得分，因为它优先考虑了得分差最大的奶酪。然而，这种方法假设了在选择的k块奶酪中不存在其他影响，例如奶酪之间的依赖性或额外的分配规则。在特殊情况或额外的约束下，这种方法可能不会得到理论上的最大总得分。因此，尽管这种方法在简单和直观的场景下有效，但它可能不适用于所有情况。

直接在reward1数组上修改得分差值是一种节省空间的做法，但这样会破坏原始数据。如果算法中的其他部分需要使用原始的reward1数据，这种修改就可能导致错误或需要额外的存储空间来保存原始数据。因此，虽然这种做法在节省空间方面有优点，但在需要多次使用原始数据的情况下可能带来问题。

如果k的值大于奶酪块数n，代码中的处理方式仍然有效。在这种情况下，由于需要选择的奶酪块数超过了实际的奶酪块数，`reward1[:k]`将简单地返回所有经过得分差值计算后的reward1元素。因此，最终的得分将是第二只老鼠的所有得分加上第一只老鼠所有奶酪的得分差，这实际上意味着第一只老鼠吃了所有奶酪。