【GESP】C++五级真题（贪心思想考点） luogu-P11960 [GESP202503 五级] 平均分配
GESP C++ 2025年3月五级真题，贪心思想考点，涉及排序，题目难度⭐⭐⭐☆☆，五级正常难度。洛谷难度等级普及/提高−
luogu-B4071 [GESP202412 五级] 武器强化
题目要求
题目描述
小 A 有 $2n$ 件物品，小 B 和小 C 想从小 A 手上买走这些物品。对于第 $i$ 件物品，小 B 会以 $b_i$ 的价格购买，而小 C 会以 $c_i$ 的价格购买。为了平均分配这 $2n$ 件物品，小 A 决定小 B 和小 C 各自只能买走恰好 $n$ 件物品。你能帮小 A 求出他卖出这 $2n$ 件物品所能获得的最大收入吗？
输入格式
第一行，一个正整数 $n$。
第二行，$2n$ 个整数 $b_1,b_2,\dots,b_{2n}$。
第三行，$2n$ 个整数 $c_1,c_2,\dots,c_{2n}$。
输出格式
一行，一个整数，表示答案。
输入输出样例 #1
输入 #1
1
2
3
3
1 3 5 6 8 10
2 4 6 7 9 11
输出 #1
1
36
输入输出样例 #2
输入 #2
1
2
3
2
6 7 9 9
1 2 10 12
输出 #2
1
35
说明/提示
数据范围
对于 $20\%$ 的测试点，保证 $1\le n\le8$。
对于另外 $20\%$ 的测试点，保证 $0\le b_i\le1$，$0\le c_i\le1$。
对于所有测试点，保证 $1\le n\le10^5$，$0\le b_i\le10^9$，$0\le c_i\le10^9$。
题目分析
解题思路
根据题目描述和提供的代码，本题采用 贪心算法 结合 排序 来解决。核心在于通过计算“差价”来决定每件物品的最优归属。
- 核心思想：差价排序 + 贪心
题目要求将 $2n$ 件物品恰好分成两组，每组 $n$ 件，分别卖给 B 和 C，使得总收入最大。我们可以采用“基准转换”的思路：
- 初始假设：首先假设 所有 $2n$ 件物品都卖给 C。此时的总收入为 $\sum c_i$。
- 计算差价：由于必须有 $n$ 件物品卖给 B，我们需要从这 $2n$ 件物品中选出 $n$ 件，将它们的买家从 C 变为 B。对于第 $i$ 件物品，如果改为卖给 B，收入的变化量为 $diff_i = b_i - c_i$。
- 如果 $b_i > c_i$，则 $diff_i > 0$，表示改卖给 B 能多赚 $diff_i$。
如果 $b_i < c_i$，则 $diff_i < 0$，表示改卖给 B 会少赚（亏损） $ diff_i $。 - 贪心选择：为了让最终总收入最大，我们应该尽可能选择 $diff_i$ 最大的那 $n$ 件物品卖给 B。
- 优先选择 $diff_i > 0$ 的物品，因为这能直接增加收入。
- 如果 $diff_i > 0$ 的物品不足 $n$ 件，或者所有物品卖给 B 都比卖给 C 亏（即所有 $diff_i < 0$），我们也必须凑足 $n$ 件。此时，选择 $diff_i$ 最大（即绝对值最小的负数）的物品，意味着“亏得最少”。
详细算法步骤
- 输入读取：读取 $n$，以及 B 和 C 对 $2n$ 件物品的出价数组 $b$ 和 $c$。
- 初始化与计算差值：
- 初始化
max_income为所有物品卖给 C 的总价（即 $\sum c_i$）。 - 计算每件物品的差价 $diff_i = b_i - c_i$，并存入
diff数组。
- 初始化
- 排序：将
diff数组从大到小排序（降序）。排序靠前的元素代表卖给 B 相对收益最高（或损失最小）。 - 贪心累加：选取排序后的前 $n$ 个差值（即最大的 $n$ 个 $b_i - c_i$），将其加到
max_income中。- 这一步操作在逻辑上等同于：将这 $n$ 件物品的归属从 C 调整为 B。
- 输出结果：最终的
max_income即为满足条件下的最大收益。
复杂度分析
- 时间复杂度：算法的瓶颈在于排序。物品总数为 $2n$，排序的时间复杂度为 $O(2n \log (2n))$，即 $O(N \log N)$。在 $N=2 \times 10^5$ 的数据范围内，计算量约为 $3.6 \times 10^6$，远小于 1 秒的时间限制。
- 空间复杂度：需要数组存储 $b$、$c$ 和 $diff$，空间复杂度为 $O(N)$。
示例代码
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <algorithm>
#include <iostream>
#include <vector>
// 定义全局数组存储小B和小C的出价，大小稍大于2*10^5
int b[200005];
int c[200005];
int main() {
int n;
// 输入n，物品总数为2n
std::cin >> n;
// 输入小B对2n件物品的出价
for (int i = 0; i < 2 * n; i++) {
std::cin >> b[i];
}
// 输入小C对2n件物品的出价
for (int i = 0; i < 2 * n; i++) {
std::cin >> c[i];
}
// diff数组存储每件物品卖给小B相比卖给小C的差价 (b[i] - c[i])
std::vector<int> diff(2 * n);
long long max_income = 0;
for (int i = 0; i < 2 * n; i++) {
// 计算差价
diff[i] = b[i] - c[i];
// 先假设所有物品都卖给小C，计算初始总收入
max_income += c[i];
}
// 将差价从大到小排序
// 差价越大，说明卖给小B越划算（或者亏得越少）
std::sort(diff.begin(), diff.end(), std::greater<int>());
// 贪心策略：选出差价最大的n件物品卖给小B
// 将这n件物品的差价加到总收入中（相当于把这n件从卖给C改为卖给B）
for (int i = 0; i < n; i++) {
max_income += diff[i];
}
// 输出最大收入
std::cout << max_income << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
