GESP 题解库 / 6 级题解 / [GESP202412 六级] 运送物资 · 第 11 / 27 题
GESP202412 六级 · P11376 · 中等

运送物资

把货车分配到各运输站点(有容量限制),使总行驶路程最短。

📊
n, m ≤ 10⁵
规模
🔢
long long
路程范围
⚡
O((n+m) log(n+m))
时间复杂度
🎯
成本拆解 + 排序贪心
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

数轴上有 A 市(坐标 0)和 B 市(坐标 x),之间有 n 个运输站点,第 i 个在坐标 pᵢ,最多容纳 cᵢ 辆车。有 m 辆货车,第 i 辆每天要向 A 市送 aᵢ 次、向 B 市送 bᵢ 次。货车从自己的站点出发、送达后返回,去 A 市的单次往返路程是 2p,去 B 市是 2(x − p)。

求最优分配下所有货车的最短总路程。

💡
人话翻译:先把"每辆车的成本"写成关于站点的式子:
cost(p) = 2p·a + 2(x−p)·b = 2p(a − b) + 2x·b。
注意 2x·b 与站点无关,是固定开销;真正要优化的是 2p(a − b)。
于是——系数 (a−b) 越大的车,越应该放在 p 越小的站点。排序后贪心分配即可。

🔍 关键词提取

成本拆解排序贪心容量约束Monge 性质

已知条件

项目说明
输入第一行 n、m、x;随后 n 行 pᵢ、cᵢ;再随后 m 行 aᵢ、bᵢ
输出最短总路程
坐标0 < pᵢ < x
容量站点 i 最多放 cᵢ 辆车
目标最小化总路程

需要解决的问题

02
思维导图
整理解题思路的全貌
🚚 拆成本 + 大配小
📐 成本化简
cost = 2pa + 2(x−p)b
= 2p(a−b) + 2xb
2xb 与站点无关(常数)
只需优化 2p(a−b)
🔑 贪心依据
d = a − b 是"斜率"
d 大 → 希望 p 小
d 小(负)→ 希望 p 大
故 d 降序配 p 升序
⚙️ 实现
货车按 d 降序排序
站点按 p 升序排序
依次填满容量
累加 2p·d,再加上常数 2xb
⚠️ 易错点
忘记加常数项 2xb
排序方向搞反
用 int(路程可达 10¹⁵)
容量没减到 0 就跳到下一个站点
03
样例手算推导
样例的完整计算

🧮 样例:n = 3,m = 4,x = 10

站点:(p=1, c=1)、(p=2, c=1)、(p=8, c=3)。

货车(aᵢ, bᵢ):(5,3)、(7,2)、(9,0)、(1,10000)。

1
第 1 步:算每辆车的 d = a − b

车 1:5 − 3 = 2

车 2:7 − 2 = 5

车 3:9 − 0 = 9

车 4:1 − 10000 = −9999

d = [9, 5, 2, −9999](降序)

2
第 2 步:站点按 p 升序

p = 1(容量 1)

p = 2(容量 1)

p = 8(容量 3)

按 p 从小到大填

3
第 3 步:依次分配

d = 9 的车 → p = 1(容量用尽)

d = 5 的车 → p = 2(容量用尽)

d = 2 的车 → p = 8(剩 2)

d = −9999 的车 → p = 8(剩 1)

分配完成

4
第 4 步:算变动的部分 Σ 2p·d

2 × (1×9 + 2×5 + 8×2 + 8×(−9999))

= 2 × (9 + 10 + 16 − 79992)

= 2 × (−79957) = −159914

−159914

5
第 5 步:加常数 Σ 2x·b

b 之和 = 3 + 2 + 0 + 10000 = 10005

2 × 10 × 10005 = 200100

常数项 200100

📊 汇总

货车abd = a−b分到站点 p贡献 2p·d
3909118
2725220
1532832
4110000−99998−159984

−159914 + 200100 = 40186 ✓

🔑
注意第 4 辆车的作用:它的 d = −9999 极小,所以应该放在最右边(p 最大)的站点——这样 2p·d 才最负,把总成本压下来。
直观理解:它主要往 B 市送(b = 10000),所以站点越靠近 B(p 越大)越省。贪心规则与直觉完全一致。

🧮 为什么"大 d 配小 p"最优

用交换论证来证明。

1
假设有两辆车 i、j 和两个站点 S、T

设 d_i > d_j 且 p_S < p_T

现在的分配是"i 在 T、j 在 S"(违背规则)

该分配贡献 = 2(d_i·p_T + d_j·p_S)

当前成本

2
交换后

改成"i 在 S、j 在 T"

新贡献 = 2(d_i·p_S + d_j·p_T)

两者之差 = 2(d_i·p_S + d_j·p_T − d_i·p_T − d_j·p_S)

= 2(d_i − d_j)(p_S − p_T)

差值计算

3
判断符号

因为 d_i > d_j,所以 (d_i − d_j) > 0

又因为 p_S < p_T,所以 (p_S − p_T) < 0

所以差值 < 0 ——即交换后总成本更小

所以"违背规则"的分配一定不是最优

✅ 得证

⚠️
这就是"排序贪心"最常用的证明套路:任取两个"逆序"的元素,证明交换它们不会让答案变差,从而说明"有序配对"是最优的。
同时也要注意:本题必须遵守容量限制,所以不能"自由配对",而是"按顺序把容量填满"——排序后的顺次填充恰好实现了最优配对。
04
解法对比
排序贪心 vs 枚举分配/网络流

⚔️ 解法对比

🟢 排序贪心(推荐) 推荐

货车按 d 降序、站点按 p 升序,顺次填容量

  • 时间 O((n+m) log(n+m))
  • n, m ≤ 10⁵ 时约 3 × 10⁶
  • 代码 30 行
  • 有交换论证保证
💡
实现要点:排序后用一个指针扫描站点,while (容量 > 0 且 还有货车) 分配,容量减到 0 就换下一个站点。注意累加时要分开处理"变动项"和"常数项",减少出错概率。

🟠 建模成最小费用流

货车为源、站点为汇,容量为边权,跑费用流

  • 理论正确
  • O(nm) 级别的复杂度
  • n, m = 10⁵ 时完全不可行
  • 属于"用重武器打小怪"
⚠️
为什么贪心就够:本题的成本矩阵是 d_i × p_j 的乘积形式,这种特殊结构使得"排序配对"必然最优。如果成本是任意的矩阵,就真的需要网络流了——所以"识别成本结构"是本题的关键。

📈 性能对比

方案复杂度可行性
排序贪心O((n+m) log(n+m))✅ 稳过
最小费用流至少 O(nm)❌ 规模太大
05
算法流程图
拆成本后排序贪心填容量
开始读入 n、m、x;读入 n 个站点 (pᵢ, cᵢ);读入 m 辆车 (aᵢ, bᵢ)常量 base = Σ 2x·bᵢ对每辆车算 dᵢ = aᵢ − bᵢ;把货车按 d 降序排序把站点按 p 升序排序;用指针 j 指向当前站点按 d 降序依次处理每辆车当前站点 j 的剩余容量是否为 0?是 ✓j 加 1,换下一个站点否 ✗直接用当前站点累加 2 × p_j × dᵢ,并把站点 j 的剩余容量减 1输出 base + 累加值处理下一辆车
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🚚 最短总路程

第一行输入 n m x,随后 n 行站点,再随后 m 行货车。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

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

struct Station { long long p, c; };
struct Truck { long long a, b, d; };

int main() {
    int n, m;
    long long x;
    scanf("%d %d %lld", &n, &m, &x);

    vector<Station> st(n);
    for (int i = 0; i < n; i++) scanf("%lld %lld", &st[i].p, &st[i].c);

    vector<Truck> tr(m);
    long long base = 0;                   // 与站点无关的常数项
    for (int i = 0; i < m; i++) {
        scanf("%lld %lld", &tr[i].a, &tr[i].b);
        tr[i].d = tr[i].a - tr[i].b;      // 关键系数
        base += 2 * x * tr[i].b;
    }

    // 货车按 d 降序
    sort(tr.begin(), tr.end(), [](const Truck &u, const Truck &v) {
        return u.d > v.d;
    });
    // 站点按 p 升序
    sort(st.begin(), st.end(), [](const Station &u, const Station &v) {
        return u.p < v.p;
    });

    long long vary = 0;
    int j = 0;
    for (int i = 0; i < m; i++) {
        while (j < n && st[j].c == 0) j++;    // 找下一个还有容量的站点
        if (j >= n) break;                    // 题目保证有解,这里作保险

        vary += 2 * st[j].p * tr[i].d;
        st[j].c--;
    }

    printf("%lld\n", base + vary);
    return 0;
}
🔑
为什么要把成本拆成两项?2p·a + 2(x−p)·b 直接看不好比较,但写成 2p(a−b) + 2x·b 后结构就清楚了:第二项完全不受站点影响,第一项则是"系数 (a−b) 乘以坐标 p"。
于是问题化为"把一组系数与一组坐标配对,使系数×坐标之和最小"——这正是"大配小"排序贪心的标准形式。

📖 关键几行怎么看

代码作用为什么这样写
tr[i].d = a - b关键系数成本的"斜率",决定该车想去哪一端
base += 2 * x * b常数项与站点无关,先拿出来
sort(tr, d 降序)货车排序d 大 → 想放左边
sort(st, p 升序)站点排序从小坐标开始填
while (st[j].c == 0) j++换站点当前站点容量用尽就往后找
⚠️
四个坑:① 忘记加常数项 2xb;② 两个排序方向搞反(货车应降序、站点应升序);③ 用 int(路程可达 10¹⁵ 量级);④ 分配时忘记扣减容量。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
3 4 10
1 1 / 2 1 / 8 3
5 3 / 7 2 / 9 0 / 1 10000
40186题面样例
1 1 10
5 1
1 1
20d = 0,故仅剩常数项 2×10×1 = 20
1 1 10
5 1
0 0
0不需要运送,路程为 0
2 1 10
3 1 / 7 1
5 0
30d = 5 应放最小的 p = 3:2×3×5 = 30
2 2 10
3 1 / 7 1
5 0 / 5 0
100两辆车相同,各自分配到站点
✅
自查清单:① 加了常数项吗?② 两个排序方向对吗?③ 扣减容量了吗?

🚨 易错点清单

⚠️
忘记常数项:2x·b 与站点无关,必须加上。
⚠️
排序方向反:货车 d 降序、站点 p 升序。
⚠️
用 int:总路程可达 10¹⁵,需要 long long。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

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

时间怎么算的?

空间都用在哪?

存站点与货车信息,各 O(n)、O(m)。

✅ 约 300 万次操作,瞬间完成。关键是把"分配问题"化简成"排序配对",避免网络流。

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

🔗 常用技巧小抄

// 本题的核心化简
// cost(p) = 2p·a + 2(x-p)·b
//         = 2p(a-b) + 2x·b
// 前半部分随 p 变化,后半部分是常数
// -> 变成"系数 d=a-b 与坐标 p 的配对问题"

// 排序配对的通用结论
// 要使 Σ d_i * p_{σ(i)} 最小:
//   d 升序 配 p 降序(即 d 大的配 p 小的)
// 要使 Σ d_i * p_{σ(i)} 最大:
//   d 升序 配 p 升序

// 交换论证模板(证明贪心正确性)
// 取任意一对"逆序"元素 i, j(d_i > d_j 但 p_i < p_j 却被反配)
// 交换后成本变化 = (d_i - d_j)(p_i - p_j)
// 由 d_i > d_j 且 p_i < p_j 得变化量为负 -> 交换更优
// 所以最优解必然"有序配对"

// 带容量约束时:排序后"顺次填满容量"即可

🌟 举一反三

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

能力点本题怎么用还能迁移到
成本拆解分离"常数项"和"可优化项"所有线性成本优化问题
排序配对大配小 / 大配大分配问题、匹配问题
交换论证证明贪心的正确性所有贪心算法的验证
🌟
思考题:如果题目变成"每个站点没有容量限制",答案会怎样?(提示:更简单——每辆车各自选择使自己成本最小的站点:d > 0 就选最小的 p,d < 0 就选最大的 p,d = 0 随便。完全不需要排序。正是"容量限制"让问题变成"排序 + 填容量",这也是本题的难度所在。)