246.平均分配

markdown
复制
1# 平均分配 题解
2
3## 题目分析
4
5小 A 有 $2n$ 件物品，对于第 $i$ 件物品，小 B 愿意出价 $b_i$，小 C 愿意出价 $c_i$。小 B 和小 C 各买走恰好 $n$ 件物品，我们需要帮助小 A 最大化总收入。
6
7等价地，我们要从 $2n$ 件物品中选择 $n$ 件卖给小 B，剩下的 $n$ 件卖给小 C，使得 $\sum\limits_{i \in \text{B}} b_i + \sum\limits_{i \in \text{C}} c_i$ 最大。
8
9如果直接枚举哪些物品给 B，复杂度为 $\binom{2n}{n}$，在 $n \le 10^5$ 时完全不可行。我们需要更高效的算法。
10
11## 解题思路
12
13一个常用的技巧是：**先假设所有物品都卖给同一个人，然后再进行调整**。
14
15假设我们把所有 $2n$ 件物品都卖给小 B，此时总收入为 $\sum_{i=1}^{2n} b_i$。
16
17但题目要求小 C 也必须买走 $n$ 件物品，所以我们需要从这 $2n$ 件物品中选出 $n$ 件，**改为**卖给小 C。对于物品 $i$，把它的买家从 B 改成 C，收入的变化量为：
18
19$$d_i = c_i - b_i$$
20
21如果 $d_i > 0$，说明改成卖给 C 能赚得更多；如果 $d_i < 0$，改卖反而会亏钱。
22
23因此，最终的总收入等于“全卖 B 的收入”加上“选出的 $n$ 件物品对应的 $d_i$ 之和”。为了让总收入最大，我们自然会选择 $d_i$ 最大的 $n$ 件物品。问题转化为：
24
25- 计算所有物品的 $d_i = c_i - b_i$；
26- 将 $d_i$ 排序，选出最大的 $n$ 个；
27- 最终答案 $= \sum_{i=1}^{2n} b_i + \sum \text{(最大的 n 个 } d_i)$。
28
29## 算法说明
30
311. 读入 $n$ 以及数组 $b[1\ldots 2n]$ 和 $c[1\ldots 2n]$。
322. 将所有 $b_i$ 累加到答案 `ans` 中。
333. 对每个 $i$，计算 $d_i = c_i - b_i$，存入数组。
344. 对 $d$ 数组从小到大排序（或直接升序）。
355. 取出最大的 $n$ 个 $d_i$（即排序后的第 $n+1$ 到第 $2n$ 个元素），累加到答案中。
366. 输出 `ans`。
37
38**正确性**：  
39由于初始假设全部给 B，然后从中选出 $n$ 件改为给 C，收益增加量正是这些物品的 $d_i$ 之和。要使总收益最大，显然应选 $d_i$ 最大的 $n$ 件物品。该算法的本质是贪心，并且可以得到全局最优解。
40
41**等价视角**：  
42也可以假设全部卖给 C，然后选出 $n$ 件改为卖给 B，此时收益增加量为 $b_i - c_i = -d_i$，选择 $b_i - c_i$ 最大的 $n$ 件等价于选择 $-d_i$ 最大的 $n$ 件，也就是选择 $d_i$ 最小的 $n$ 件。两种视角结果一致，只是排序和选择的区间不同。
43
44## 时间复杂度分析
45
46- 计算 $b_i$ 总和、计算 $d_i$：$O(n)$；
47- 排序 $d$ 数组：$O(n \log n)$；
48- 累加最大的 $n$ 个 $d_i$：$O(n)$。
49
50总时间复杂度 $O(n \log n)$，当 $n=10^5$ 时，可以在 1 秒内轻松通过。空间复杂度 $O(n)$。
51
52**注意**：  
53数据范围中的 $b_i, c_i$ 最大可到 $10^9$，$2n$ 件物品总和可能达到 $2 \times 10^5 \times 10^9 = 2 \times 10^{14}$，需要使用 64 位整型（`long long`）存储答案和差值。
54
55## 参考代码
56
57```cpp
58#include <bits/stdc++.h>
59using namespace std;
60
61const int N = 2e5 + 5;    // 最大 2n
62
63int n;
64long long b[N], c[N], d[N];
65long long ans;
66
67int main() {
68    // 读入 n
69    scanf("%d", &n);
70    
71    // 读入 b 数组
72    for (int i = 1; i <= 2 * n; i++) {
73        scanf("%lld", &b[i]);
74    }
75    // 读入 c 数组
76    for (int i = 1; i <= 2 * n; i++) {
77        scanf("%lld", &c[i]);
78    }
79
80    // 计算全卖 B 的收入，以及差值 d
81    for (int i = 1; i <= 2 * n; i++) {
82        ans += b[i];
83        d[i] = c[i] - b[i];
84    }
85
86    // 对差值排序（升序）
87    sort(d + 1, d + 2 * n + 1);
88
89    // 选出最大的 n 个差值加入答案
90    for (int i = n + 1; i <= 2 * n; i++) {
91        ans += d[i];
92    }
93
94    // 输出结果
95    printf("%lld\n", ans);
96    return 0;
97}

代码解释

• ans：用于累加总收入，初始设为 $\sum b_i$。
• d[i] = c[i] - b[i]：保存将物品 $i$ 从卖给 B 改为卖给 C 的收益变化。
• sort(d + 1, d + 2 * n + 1)：将 $d$ 数组按升序排列。此时下标 $1\sim 2n$ 中，后半部分 $n+1\sim 2n$ 就是最大的 $n$ 个值。
• 最后的循环将这 $n$ 个最大值加到 ans 上，得到最终的最大收入。
• 使用 %lld 和 long long 避免溢出。
• 数组大小开到 2e5+5，足够容纳最大规模的 $2 \times 10^5$ 个元素。

小结

本题是一道经典的“分配物品使总和最大”的贪心问题。核心思想是先固定一个分配方案，再通过计算“改变分配带来的收益差”来调整。整个过程只需要一次排序，实现简单且高效。