题目描述：
有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。
下标为 i 处的奶酪被吃掉的得分为：
- 如果第一只老鼠吃掉，则得分为
reward1[i] 。 - 如果第二只老鼠吃掉，则得分为
reward2[i] 。
给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。
请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。
数据范围：
$1\le len \le 10^5, 1\le k \le n$
题解：
假设已经得到了一个解，那么如果转换一下其中的 $j$ ，如果之前是选择的 $1$ ，那么就会变成 $-reward1[j] + reward2[j]$ ，就得到了另一个解。因此可以贪心的操作，先假设全吃的 $2$ ，然后选最大的 $k$ 个进行转换。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
const static long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const static long long mod = 1e9 + 7;
int miceAndCheese(vector<int> &reward1, vector<int> &reward2, int k)
{
int n = reward1.size();
int sum2 = accumulate(reward2.begin(), reward2.end(), 0);
vector<pair<int, int>> nums(n);
for (int i = 0; i < n; ++i)
nums[i] = {reward1[i], reward2[i]};
sort(nums.begin(), nums.end(), [&](const pair<int, int> &x, const pair<int, int> &y)
{ return x.first - x.second > y.first - y.second; });
for (int i = 0; i < k; ++i)
{
sum2 += nums[i].first - nums[i].second;
}
return sum2;
}
};
|