What is the greedy strategy for 'Mice and Cheese'?

In 'Mice and Cheese', the greedy strategy involves sorting the cheese types by the difference in rewards and then assigning the best k cheeses to the first mouse, maximizing the total reward.

How do we handle the constraint on k in the problem?

The first mouse can eat at most k cheeses, so we choose the top k cheeses with the highest reward for the first mouse and assign the rest to the second mouse.

What is the time complexity of the optimal solution for 'Mice and Cheese'?

The optimal solution has a time complexity of O(n log n) due to the sorting step of the cheese rewards, where n is the number of cheese types.

Can the greedy approach for 'Mice and Cheese' fail?

The greedy approach is optimal for this problem, as long as we correctly choose the top k cheeses for the first mouse and respect the problem constraints.

What are some possible variations of the 'Mice and Cheese' problem?

Possible variations include changing the number of mice, adjusting the value of k, or introducing more complex constraints on cheese assignments.

#2611

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

老鼠和奶酪

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。下标为 i 处的奶酪被吃掉的得分为：如果第一只老鼠吃掉，则得分为 reward1[i] 。如果第二只老鼠吃掉，则得分为 reward2[i] 。给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个…

数组贪心排序堆（优先队列）

题目描述

有两只老鼠和 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

lightbulb

解题思路

方法一：贪心 + 排序

我们可以先将所有奶酪分给第二只老鼠，因此初始得分为 $\sum_{i=0}^{n-1} reward2[i]$ 。

接下来，考虑将其中 $k$ 块奶酪分给第一只老鼠，那么我们应该如何选择这 $k$ 块奶酪呢？显然，将第 $i$ 块奶酪从第二只老鼠分给第一只老鼠，得分的变化量为 $reward1[i] - reward2[i]$ ，我们希望这个变化量尽可能大，这样才能使得总得分最大。

因此，我们将奶酪按照 $reward1[i] - reward2[i]$ 从大到小排序，前 $k$ 块奶酪由第一只老鼠吃掉，剩下的奶酪由第二只老鼠吃掉，即可得到最大得分。也即是说，我们将初始得分加上 $\sum_{i=0}^{k-1} (reward1[i] - reward2[i])$ 即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为奶酪的数量。

相似题目：

1029. 两地调度

1

2

3

4

5

6

class Solution:
    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:
        n = len(reward1)
        idx = sorted(range(n), key=lambda i: reward1[i] - reward2[i], reverse=True)
        return sum(reward1[i] for i in idx[:k]) + sum(reward2[i] for i in idx[k:])

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Test the candidate's understanding of greedy algorithms and their ability to handle sorting in optimization problems.
question_mark
Evaluate if the candidate can recognize the pattern of greedy choice plus invariant validation and apply it correctly.
question_mark
Look for understanding of the trade-off between the first mouse's reward and the second mouse's reward, ensuring the final solution is maximized.

warning

常见陷阱

外企场景

error
Incorrectly assigning cheese types to both mice, ignoring the greedy approach that maximizes rewards.
error
Forgetting to validate that the first mouse eats at most k cheeses, which could violate the problem's constraints.
error
Neglecting to account for sorting the cheese reward differences before assignment, leading to suboptimal solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the constraint on k, allowing for more or fewer cheeses for the first mouse to eat.
arrow_right_alt
Modify the problem by having more than two mice, testing the scalability of the approach.
arrow_right_alt
Alter the reward arrays to introduce some randomness or additional constraints to test robustness.

help

常见问题

外企场景

继续练习

#2551 将珠子放入背包中 #2542 最大子序列的分数 #2497 图中最大星和