class Solution {
public:
int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
}
};
2611. 老鼠和奶酪
有两只老鼠和 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 <= 1051 <= reward1[i], reward2[i] <= 10000 <= k <= n原站题解
golang 解法, 执行用时: 124 ms, 内存消耗: 9.2 MB, 提交时间: 2023-04-11 09:40:44
func miceAndCheese(reward1, reward2 []int, k int) (ans int) {
for i, x := range reward2 {
ans += x // 全部给第二只老鼠
reward1[i] -= x
}
sort.Sort(sort.Reverse(sort.IntSlice(reward1)))
for _, x := range reward1[:k] {
ans += x
}
return
}
java 解法, 执行用时: 12 ms, 内存消耗: 50.4 MB, 提交时间: 2023-04-11 09:40:28
class Solution {
public int miceAndCheese(int[] r1, int[] r2, int k) {
int ans = 0, n = r1.length;
for (int i = 0; i < n; ++i) {
ans += r2[i]; // 全部给第二只老鼠
r1[i] -= r2[i];
}
Arrays.sort(r1);
for (int i = n - k; i < n; ++i)
ans += r1[i];
return ans;
}
}
python3 解法, 执行用时: 112 ms, 内存消耗: 26.3 MB, 提交时间: 2023-04-11 09:40:05
'''
贪心策略：r1[i] - r2[i] 更大的，给第一只老鼠；
按r1[i] - r2[i] 逆序排序，前k给第一只老鼠，剩余给第二只老鼠。
'''
class Solution:
def miceAndCheese(self, r1: List[int], r2: List[int], k: int) -> int:
for i, x in enumerate(r2):
r1[i] -= x
r1.sort(reverse=True)
return sum(r2) + sum(r1[:k]) # 忽略切片空间
python3 解法, 执行用时: 160 ms, 内存消耗: 33.5 MB, 提交时间: 2023-04-11 09:39:50
'''
贪心策略：r1[i] - r2[i] 更大的，给第一只老鼠；
按r1[i] - r2[i] 逆序排序，前k给第一只老鼠，剩余给第二只老鼠。
'''
class Solution:
def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:
a = sorted(zip(reward1, reward2), key=lambda p: p[1] - p[0])
return sum(x for x, _ in a[:k]) + sum(y for _, y in a[k:])