老鼠和奶酪
难度:
标签:
题目描述
There are two mice and n different types of cheese, each type of cheese should be eaten by exactly one mouse.
A point of the cheese with index i (0-indexed) is:
reward1[i]if the first mouse eats it.reward2[i]if the second mouse eats it.
You are given a positive integer array reward1, a positive integer array reward2, and a non-negative integer k.
Return the maximum points the mice can achieve if the first mouse eats exactly k types of cheese.
Example 1:
Input: reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2 Output: 15 Explanation: In this example, the first mouse eats the 2nd (0-indexed) and the 3rd types of cheese, and the second mouse eats the 0th and the 1st types of cheese. The total points are 4 + 4 + 3 + 4 = 15. It can be proven that 15 is the maximum total points that the mice can achieve.
Example 2:
Input: reward1 = [1,1], reward2 = [1,1], k = 2 Output: 2 Explanation: In this example, the first mouse eats the 0th (0-indexed) and 1st types of cheese, and the second mouse does not eat any cheese. The total points are 1 + 1 = 2. It can be proven that 2 is the maximum total points that the mice can achieve.
Constraints:
1 <= n == reward1.length == reward2.length <= 1051 <= reward1[i], reward2[i] <= 10000 <= k <= n
代码结果
运行时间: 80 ms, 内存: 27.7 MB
/*
* 思路：我们需要在第一只老鼠吃掉 k 块奶酪的情况下，最大化总得分。
* 为了实现这一点，我们可以计算每块奶酪对两只老鼠得分的差值，然后根据差值排序，选择最适合的奶酪。
* 1. 计算每块奶酪 reward1 和 reward2 的差值。
* 2. 根据差值对奶酪进行排序，优先让得分差距大的奶酪被第一只老鼠吃掉。
* 3. 计算前 k 块奶酪让第一只老鼠吃掉的总得分，剩下的奶酪让第二只老鼠吃掉。
*/
import java.util.stream.IntStream;
public int maxScore(int[] reward1, int[] reward2, int k) {
int n = reward1.length;
int[] indices = IntStream.range(0, n)
.boxed()
.sorted((a, b) -> (reward2[b] - reward1[b]) - (reward2[a] - reward1[a]))
.mapToInt(i -> i)
.toArray();
int totalScore = 0;
totalScore += IntStream.range(0, k).map(i -> reward1[indices[i]]).sum();
totalScore += IntStream.range(k, n).map(i -> reward2[indices[i]]).sum();
return totalScore;
}解释
方法:
题解的思路是通过计算每块奶酪被第一只老鼠吃与第二只老鼠吃的得分差值来决定分配。首先，将每块奶酪的得分差值计算出来，并与原有第二只老鼠的得分数组结合。差值大的奶酪优先被第一只老鼠吃，因为这样可以最大化总得分。最后，根据差值排序，取出差值最大的前k块奶酪的差值，再加上所有奶酪的第二只老鼠的得分，得到最终的最大得分。
时间复杂度:
O(n log n)
空间复杂度:
O(log n)
代码细节讲解
🦆
为什么在计算奶酪分配的优先级时，选择使用奶酪的得分差值而不是直接比较reward1和reward2的具体数值？
▷🦆
在题解中提到`差值大的奶酪优先被第一只老鼠吃`，这种方法在所有情况下都能保证得到最大总得分吗？
▷🦆
代码实现中直接修改了reward1数组来存储得分差值，这种做法是否有可能影响到算法的其他部分或在某些情况下造成数据的误用？
▷🦆
如果k的值大于奶酪块数n，代码中的这种处理方式是否仍然有效？
▷