202503-平均分配(luogu-P11960)

GESP C++ 2025年3月五级真题，贪心思想考点，涉及排序，题目难度⭐⭐⭐☆☆，五级正常难度。洛谷难度等级普及/提高−

luogu-P11960 [GESP202503 五级] 平均分配

题目要求

题目描述

小 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

3
1 3 5 6 8 10
2 4 6 7 9 11

输出 #1

36

输入输出样例 #2

输入 #2

2
6 7 9 9
1 2 10 12

输出 #2

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$。

题目分析

解题思路

根据题目描述和提供的代码，本题采用 贪心算法 结合 排序 来解决。核心在于通过计算“差价”来决定每件物品的最优归属。

1. 核心思想：差价排序 + 贪心

题目要求将 $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$ 最大（即绝对值最小的负数）的物品，意味着“亏得最少”。

2. 详细算法步骤

   1. 输入读取：读取 $n$，以及 B 和 C 对 $2n$ 件物品的出价数组 $b$ 和 $c$。
   2. 初始化与计算差值：
      • 初始化 max_income 为所有物品卖给 C 的总价（即 $\sum c_i$）。
      • 计算每件物品的差价 $diff_i = b_i - c_i$，并存入 diff 数组。
   3. 排序：将 diff 数组从大到小排序（降序）。排序靠前的元素代表卖给 B 相对收益最高（或损失最小）。
   4. 贪心累加：选取排序后的前 $n$ 个差值（即最大的 $n$ 个 $b_i - c_i$），将其加到 max_income 中。
      • 这一步操作在逻辑上等同于：将这 $n$ 件物品的归属从 C 调整为 B。
   5. 输出结果：最终的 max_income 即为满足条件下的最大收益。

3. 复杂度分析

   • 时间复杂度：算法的瓶颈在于排序。物品总数为 $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)$。

示例代码

#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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号