老鼠和奶酪
有两只老鼠和 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^5\)
1 <= reward1[i], reward2[i] <= 1000
0 <= k <= n
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/mice-and-cheese
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
贪心。首先假设所有的奶酪都是第二只老鼠吃掉的,也就是sum(reward2),加入将其中的一个给第一只老鼠吃掉,sum(reward2) - reward2[i] + reward1[i],其中的变化量是reward1[i] - reward2[i],变化量当然是越大越好,所以预处理出变换量,从大到小选择k个即可。
code
class Solution {
public:
//k = 0,sum(reward2)
//k = 1,sum(reward2) - reward2[i] + reward1[i] = sum(reward2) + reward1[i] - reward2[i]
//.....
//每次选择reward1[i] - reward2[i]最大值
int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
int n = reward1.size();
int diff[n];
long long int sum2 = 0;
for(int i = 0;i < n;i ++) diff[i] = reward1[i] - reward2[i],sum2 += reward2[i];
sort(diff,diff + n);
for(int i = 0;i < k;i ++)
{
sum2 += diff[n - i - 1];
}
return sum2;
}
};