题目链接：2611. 老鼠和奶酪
方法：贪心
解题思路
题目要求第\(mouse1\)恰好吃掉 \(k\) 块奶酪的情况下，计算最大得分。
- 假设\(mouse1\)当前吃掉了下标为\(i\)处的奶酪，那么应该满足，\(diff[i] = reward1[i] - reward2[i]\)是当前所有\(diff\)值的最大值，这样就可以保证\(mouse1\)吃掉当前的奶酪，为得分做出"最大贡献"；
- 我们可以假设所有奶酪都被\(mouse2\)吃掉，然后再加上\(diff\)数组中的前\(k\)个最大值，就表示相应的奶酪让\(mouse1\)吃掉。
代码
class Solution {
public:
int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
int n = reward1.size();
vector<int> diff(n);
int score = 0;
for (int i = 0; i < n; i ++ ) {
diff[i] = reward1[i] - reward2[i];
score += reward2[i];
}
sort(diff.begin(), diff.end(), greater<int>());
int idx = 0;
while (idx < k) score += diff[idx ++ ];
return score;
}
};
复杂度分析
时间复杂度：\(O(nlogn)\)；
空间复杂度：\(O(n)\)。