GESP 题解库 / 5 级题解 / [GESP202503 五级] 平均分配 · 第 10 / 23 题
GESP202503 五级 · P11960 · 中等

平均分配

2n 件物品,B 和 C 各买 n 件,求最大总收入。

📊
n ≤ 10⁵
物品对数
🔢
long long
数值类型
⚡
O(n log n)
时间复杂度
🎯
差价排序取前 n 大
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

有 2n 件物品。第 i 件物品,小 B 出价 bᵢ、小 C 出价 cᵢ。小 A 决定小 B 和小 C 各自恰好买走 n 件。求能获得的最大总收入。

💡
人话翻译:每件物品只有一个买家(要么 B 要么 C),而且两个买家都必须恰好买 n 件。关键转化:先假设所有物品都给 B,此时收入是 Σbᵢ;然后要"改判"恰好 n 件给 C,每改一件的收益变化是 cᵢ − bᵢ;所以只需挑出差价最大的 n 件改判给 C。

🔍 关键词提取

贪心差价排序恰好 n 件的约束转化思路

已知条件

项目说明
输入第一行 n;第二行 2n 个 bᵢ;第三行 2n 个 cᵢ
输出最大总收入
数据范围1 ≤ n ≤ 10⁵
价格范围0 ≤ bᵢ, cᵢ ≤ 10⁵
约束B 恰好买 n 件、C 恰好买 n 件

需要解决的问题

02
思维导图
整理解题思路的全貌
💰 选 n 件最大差价改判
🧠 转化
基准:全部卖给 B
基准收入 = Σbᵢ
需要改判恰好 n 件给 C
问题变成"选 n 件最优"
📊 差价
dᵢ = cᵢ − bᵢ
改判收益就是 dᵢ
要最大化 Σ 选中的 dᵢ
选最大的 n 个
✅ 答案
答案 = Σbᵢ + (前 n 大的 dᵢ 之和)
差价可能为负也必须选够 n 件
因为 C 必须恰好买 n 件
不能只选正的
⚠️ 易错点
只选正的差价(导致 C 买不到 n 件)
用 int(Σb 可达 2×10¹⁰)
排序方向搞反
忘记恰好 n 件的硬约束
03
样例手算推导
两个样例的完整计算

🧮 样例 1:n = 3,b = [1,3,5,6,8,10],c = [2,4,6,7,9,11]

先算基准收入,再算各件差价。

物品bᵢcᵢ差价 dᵢ = cᵢ − bᵢ
112+1
234+1
356+1
467+1
589+1
61011+1
1
基准收入

Σbᵢ = 1 + 3 + 5 + 6 + 8 + 10 = 33

基准 33

2
选 3 件改判

所有差价都是 +1

选任意 3 件改判给 C,总收益 = 3 × 1 = 3

改判收益 3

3
合计

33 + 3 = 36

✅ 答案 36

36 ✓

🧮 样例 2:n = 2,b = [6,7,9,9],c = [1,2,10,12]

这组数据里有负差价,正好考察"必须选够 n 件"这个约束。

物品bᵢcᵢ差价 dᵢ
161−5
272−5
3910+1
4912+3
1
基准收入

Σbᵢ = 6 + 7 + 9 + 9 = 31

基准 31

2
排序差价

差价排序后:+3、+1、−5、−5

取前 n = 2 大:+3 和 +1

改判收益 = 3 + 1 = 4

改判收益 4

3
合计

31 + 4 = 35

✅ 答案 35

35 ✓

⚠️
关键点:即使差价是负数,也必须选够 n 件!因为题目硬性要求"C 恰好买 n 件"。在更极端的数据下(比如所有差价都是负的),答案就是 Σbᵢ 加上前 n 大差价(可能全为负)——这时的答案会小于 Σbᵢ,但这是"必须满足约束"的结果,不能为了让收入更高而少选。
04
解法对比
差价排序 vs 动态规划

⚔️ 解法对比

🟢 差价排序(推荐) 推荐

算 Σb,再把 d = c − b 排序取前 n 大相加

  • 时间 O(n log n)
  • n = 10⁵ 时约 10⁶ 次
  • 代码 10 行
  • 有清晰的贪心证明
💡
为什么贪心最优:答案 = Σbᵢ + (选中的 dᵢ 之和),其中 Σbᵢ 是常数,所以只需最大化"选中 d 之和"。在"恰好选 n 个"的约束下,显然选最大的 n 个最优。

🟠 动态规划

dp[i][j] 表示前 i 件物品中 C 选了 j 件的最大收益

  • 时间 O(n²) 或 O(n × n) = 10¹⁰
  • 超时
  • 逻辑正确但过慢
  • 属于杀鸡用牛刀
⚠️
为什么不需要 DP:本题没有复杂的依赖关系——每件物品的选择彼此独立,只受"总数恰好 n"这个约束,所以贪心就够了。有 DP 可用不代表一定要用 DP。

📈 性能对比

方案复杂度(n = 10⁵)可行性
差价排序约 10⁶✅ 稳过
二维 DP约 10¹⁰❌ 超时
05
算法流程图
算基准与差价,排序取前 n
开始读入 n 和数组 b、c(各 2n 个)base = Σbᵢ(全部卖给 B 的收入)对每件物品计算差价 dᵢ = cᵢ − bᵢ把差价数组从大到小排序,取前 n 个求和 gain答案 = base + gain结束逐件计算差价
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

💰 最大收入计算器

第一行输入 n,第二行输入 B 的报价,第三行输入 C 的报价。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

long long b[200005], c[200005];

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < 2 * n; i++) scanf("%lld", &b[i]);
    for (int i = 0; i < 2 * n; i++) scanf("%lld", &c[i]);

    // 基准:全部卖给 B
    long long ans = 0;
    vector<long long> d(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        ans += b[i];
        d[i] = c[i] - b[i];        // 改判给 C 的收益变化
    }

    // 取差价最大的 n 个
    sort(d.begin(), d.end(), greater<long long>());
    for (int i = 0; i < n; i++) ans += d[i];

    printf("%lld\n", ans);
    return 0;
}
🔑
为什么"选最大的 n 个差价"是最优的?因为答案可以写成 Σbᵢ + Σ_{i∈S} dᵢ,其中 Σbᵢ 是固定值,S 是"改判给 C"的 n 件物品集合。要让总和最大,就只需让 Σdᵢ 尽量大;在"必须选 n 个"的约束下,显然取最大的 n 个 dᵢ。这是贪心的经典论证方式:把常数项剥离,只优化可控部分。

📖 关键几行怎么看

代码作用为什么这样写
ans += b[i]基准收入先假设全给 B
d[i] = c[i] - b[i]差价改判给 C 的收益变化
sort(d, d+2n, greater<long long>())降序排序取最大的 n 个
for (i = 0; i < n; i++) ans += d[i]累加改判收益恰好 n 个,不管正负
⚠️
三个坑:① 只累加正差价(会导致 C 买不到 n 件,违反约束);② 用 int(Σb 可达 2 × 10⁵ × 10⁵ = 2 × 10¹⁰,会溢出);③ 排序写成升序(应该取最大的 n 个)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
1 3 5 6 8 10
2 4 6 7 9 11
36题面样例 1
2
6 7 9 9
1 2 10 12
35题面样例 2(含负差价)
1
5 7
3 9
14n = 1:基准 12,差价 [−2, +2],取 +2 → 14
1
10 1
1 10
20B 买贵的、C 买另一件,各得其所
2
0 0 0 0
0 0 0 0
0全为 0
✅
自查清单:① 基准是 Σb 吗?② 取的是恰好 n 个差价吗?③ 用 long long 吗?

🚨 易错点清单

⚠️
只选正差价:C 必须恰好买 n 件,所以即使差价是负数也必须选够。
⚠️
用 int:Σb 可达 2 × 10¹⁰,超过 int 上限,必须用 long long。
⚠️
排序方向错:要取最大的 n 个,所以用降序排序(或升序后从末尾取)。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log n)
空间复杂度
O(n)
n 最大
10⁵
运算量
约 10⁶

时间怎么算的?

空间都用在哪?

需要存 b、c 和差价数组,各 2n 个 long long。

✅ 约 100 万次操作,瞬间完成。如果写成 O(n²) 的 DP,10¹⁰ 次会超时。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 贪心论证模板:把答案拆成"常数项 + 可控项"
// 本题:答案 = Σb (常数) + Σ_{选中} d  (可控)
// 约束:"恰好选 n 个" -> 取最大的 n 个 d

// 降序排序的三种写法
sort(d.begin(), d.end(), greater<long long>());          // 方式一
sort(d.begin(), d.end());                                 // 方式二:升序后排
for (int i = 2 * n - 1, c = 0; c < n; i--, c++) ans += d[i];
sort(d.rbegin(), d.rend());                              // 方式三:反向迭代器

// 类似题目
// "选 n 件最大化差价""两方分配最大化收益"等
// 都属于"独立选择 + 数量约束"的贪心模型

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
贪心拆解常数项 + 可控项预算分配、双向报价类问题
恰好 n 件约束必须选够,不管正负所有"配额"类问题的关键
差价转化c − b 表示改判收益选择问题、交换优化的通用技巧
🌟
思考题:如果题目去掉了"各买 n 件"的约束(即每件物品可以卖给任何人,也可以不卖),答案会怎样?(提示:那就简单多了——每件物品独立地选 max(bᵢ, cᵢ) 即可,答案是 Σ max(bᵢ, cᵢ),甚至不需要排序。正是"恰好 n 件"这个配额约束,才让题目需要排序贪心。)