把货车分配到各运输站点(有容量限制),使总行驶路程最短。
数轴上有 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)。成本拆解排序贪心容量约束Monge 性质
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m、x;随后 n 行 pᵢ、cᵢ;再随后 m 行 aᵢ、bᵢ |
| 输出 | 最短总路程 |
| 坐标 | 0 < pᵢ < x |
| 容量 | 站点 i 最多放 cᵢ 辆车 |
| 目标 | 最小化总路程 |
2p·a + 2(x−p)·b = 2p(a−b) + 2x·b;后半部分是常数d = a − b 从大到小排序,把站点按 p 从小到大排序,然后依次"填满"站点容量d_i × p_j 满足"越大配越小"的单调性,可以用交换论证证明站点:(p=1, c=1)、(p=2, c=1)、(p=8, c=3)。
货车(aᵢ, bᵢ):(5,3)、(7,2)、(9,0)、(1,10000)。
车 1:5 − 3 = 2
车 2:7 − 2 = 5
车 3:9 − 0 = 9
车 4:1 − 10000 = −9999
d = [9, 5, 2, −9999](降序)
p = 1(容量 1)
p = 2(容量 1)
p = 8(容量 3)
按 p 从小到大填
d = 9 的车 → p = 1(容量用尽)
d = 5 的车 → p = 2(容量用尽)
d = 2 的车 → p = 8(剩 2)
d = −9999 的车 → p = 8(剩 1)
分配完成
2 × (1×9 + 2×5 + 8×2 + 8×(−9999))
= 2 × (9 + 10 + 16 − 79992)
= 2 × (−79957) = −159914
−159914
b 之和 = 3 + 2 + 0 + 10000 = 10005
2 × 10 × 10005 = 200100
常数项 200100
| 货车 | a | b | d = a−b | 分到站点 p | 贡献 2p·d |
|---|---|---|---|---|---|
| 3 | 9 | 0 | 9 | 1 | 18 |
| 2 | 7 | 2 | 5 | 2 | 20 |
| 1 | 5 | 3 | 2 | 8 | 32 |
| 4 | 1 | 10000 | −9999 | 8 | −159984 |
−159914 + 200100 = 40186 ✓
2p·d 才最负,把总成本压下来。用交换论证来证明。
设 d_i > d_j 且 p_S < p_T
现在的分配是"i 在 T、j 在 S"(违背规则)
该分配贡献 = 2(d_i·p_T + d_j·p_S)
当前成本
改成"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)
差值计算
因为 d_i > d_j,所以 (d_i − d_j) > 0
又因为 p_S < p_T,所以 (p_S − p_T) < 0
所以差值 < 0 ——即交换后总成本更小
所以"违背规则"的分配一定不是最优
✅ 得证
货车按 d 降序、站点按 p 升序,顺次填容量
while (容量 > 0 且 还有货车) 分配,容量减到 0 就换下一个站点。注意累加时要分开处理"变动项"和"常数项",减少出错概率。货车为源、站点为汇,容量为边权,跑费用流
d_i × p_j 的乘积形式,这种特殊结构使得"排序配对"必然最优。如果成本是任意的矩阵,就真的需要网络流了——所以"识别成本结构"是本题的关键。| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 排序贪心 | O((n+m) log(n+m)) | ✅ 稳过 |
| 最小费用流 | 至少 O(nm) | ❌ 规模太大 |
第一行输入 n m x,随后 n 行站点,再随后 m 行货车。
点按钮开始 →
#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¹⁵ 量级);④ 分配时忘记扣减容量。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 4 10 | 40186 | 题面样例 |
1 1 10 | 20 | d = 0,故仅剩常数项 2×10×1 = 20 |
1 1 10 | 0 | 不需要运送,路程为 0 |
2 1 10 | 30 | d = 5 应放最小的 p = 3:2×3×5 = 30 |
2 2 10 | 100 | 两辆车相同,各自分配到站点 |
2x·b 与站点无关,必须加上。存站点与货车信息,各 O(n)、O(m)。
✅ 约 300 万次操作,瞬间完成。关键是把"分配问题"化简成"排序配对",避免网络流。
// 本题的核心化简 // 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 随便。完全不需要排序。正是"容量限制"让问题变成"排序 + 填容量",这也是本题的难度所在。)