题目描述
有两只老鼠和 n
块不同类型的奶酪,每块奶酪都只能被其中一只老鼠吃掉。
下标为 i
处的奶酪被吃掉的得分为:
- 如果第一只老鼠吃掉,则得分为
reward1[i]
。 - 如果第二只老鼠吃掉,则得分为
reward2[i]
。
给你一个正整数数组 reward1
,一个正整数数组 reward2
,和一个非负整数 k
。
请你返回第一只老鼠恰好吃掉 k
块奶酪的情况下,最大 得分为多少。
样例
输入:reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
输出:15
解释:这个例子中,第一只老鼠吃掉第 2 和 3 块奶酪(下标从 0 开始),第二只老鼠吃掉第 0 和 1 块奶酪。
总得分为 4 + 4 + 3 + 4 = 15。
15 是最高得分。
输入: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
算法
(贪心,堆) $O(n \log k)$
- 显然,第一只老鼠选择吃掉 $reward1 - reward2$ 差值最大的 $k$ 块奶酪,可以使得总得分最大。
- 维护一个容量为 $k$ 的小跟堆,存储当前差值最大的 $k$ 块奶酪(第一只老鼠吃的奶酪)。
- 遍历数组,令这块奶酪给第一只老鼠吃,并将当前差值进堆。如果堆的容量超出了 $k$,则最小差值的奶酪出堆,交给第二只老鼠吃。
时间复杂度
- 遍历数组一次,每次遍历需要 $O(\log k)$ 的时间操作堆,故时间复杂度为 $O(n \log k)$。
空间复杂度
- 需要 $O(k)$ 的额外空间存储堆。
C++ 代码
blablclass Solution {
public:
int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
const int n = reward1.size();
priority_queue<int, vector<int>, greater<int>> heap;
int ans = 0;
for (int i = 0; i < n; i++) {
ans += reward1[i];
heap.push(reward1[i] - reward2[i]);
if (heap.size() > k) {
int t = heap.top();
heap.pop();
ans -= t;
}
}
return ans;
}
};abla