2n 件物品,B 和 C 各买 n 件,求最大总收入。
有 2n 件物品。第 i 件物品,小 B 出价 bᵢ、小 C 出价 cᵢ。小 A 决定小 B 和小 C 各自恰好买走 n 件。求能获得的最大总收入。
cᵢ − bᵢ;所以只需挑出差价最大的 n 件改判给 C。贪心差价排序恰好 n 件的约束转化思路
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 2n 个 bᵢ;第三行 2n 个 cᵢ |
| 输出 | 最大总收入 |
| 数据范围 | 1 ≤ n ≤ 10⁵ |
| 价格范围 | 0 ≤ bᵢ, cᵢ ≤ 10⁵ |
| 约束 | B 恰好买 n 件、C 恰好买 n 件 |
cᵢ − bᵢ先算基准收入,再算各件差价。
| 物品 | bᵢ | cᵢ | 差价 dᵢ = cᵢ − bᵢ |
|---|---|---|---|
| 1 | 1 | 2 | +1 |
| 2 | 3 | 4 | +1 |
| 3 | 5 | 6 | +1 |
| 4 | 6 | 7 | +1 |
| 5 | 8 | 9 | +1 |
| 6 | 10 | 11 | +1 |
Σbᵢ = 1 + 3 + 5 + 6 + 8 + 10 = 33
基准 33
所有差价都是 +1
选任意 3 件改判给 C,总收益 = 3 × 1 = 3
改判收益 3
33 + 3 = 36
✅ 答案 36
36 ✓
这组数据里有负差价,正好考察"必须选够 n 件"这个约束。
| 物品 | bᵢ | cᵢ | 差价 dᵢ |
|---|---|---|---|
| 1 | 6 | 1 | −5 |
| 2 | 7 | 2 | −5 |
| 3 | 9 | 10 | +1 |
| 4 | 9 | 12 | +3 |
Σbᵢ = 6 + 7 + 9 + 9 = 31
基准 31
差价排序后:+3、+1、−5、−5
取前 n = 2 大:+3 和 +1
改判收益 = 3 + 1 = 4
改判收益 4
31 + 4 = 35
✅ 答案 35
35 ✓
算 Σb,再把 d = c − b 排序取前 n 大相加
dp[i][j] 表示前 i 件物品中 C 选了 j 件的最大收益
| 方案 | 复杂度(n = 10⁵) | 可行性 |
|---|---|---|
| 差价排序 | 约 10⁶ | ✅ 稳过 |
| 二维 DP | 约 10¹⁰ | ❌ 超时 |
第一行输入 n,第二行输入 B 的报价,第三行输入 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; }
Σ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 个,不管正负 |
int(Σb 可达 2 × 10⁵ × 10⁵ = 2 × 10¹⁰,会溢出);③ 排序写成升序(应该取最大的 n 个)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 36 | 题面样例 1 |
2 | 35 | 题面样例 2(含负差价) |
1 | 14 | n = 1:基准 12,差价 [−2, +2],取 +2 → 14 |
1 | 20 | B 买贵的、C 买另一件,各得其所 |
2 | 0 | 全为 0 |
需要存 b、c 和差价数组,各 2n 个 long long。
✅ 约 100 万次操作,瞬间完成。如果写成 O(n²) 的 DP,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 表示改判收益 | 选择问题、交换优化的通用技巧 |
Σ max(bᵢ, cᵢ),甚至不需要排序。正是"恰好 n 件"这个配额约束,才让题目需要排序贪心。)