贪心算法实战：P11376运送物资题解与C++实现

1. 项目概述与问题核心最近在刷GESP六级和信奥的题目遇到一道挺有意思的贪心算法题——P11376 “运送物资”。这道题初看描述有点绕什么货车、站点、A市B市但本质上是一个关于“如何给多辆货车分配初始站点使得所有货车每天的总行驶路程最短”的优化问题。我花了些时间研究发现它的核心在于对“成本差值”的排序和“站点资源”的匹配是一个典型的贪心选择问题用C实现起来代码量不大但思维过程值得细细拆解。简单来说题目给了你n个运输站点每个站点有位置p和容量c、m辆货车每辆车有去A市的次数a和去B市的次数b以及A、B两市在数轴上的固定位置A在0B在x。每辆货车必须固定从一个站点出发完成它当天所有的运输任务去A或去B后再回到这个站点。我们的目标就是给每辆车分配一个初始站点不能超过站点容量让所有车加起来跑的总路程最少。为什么说它有意思因为每辆车去A和去B的成本单次行驶路程只和它选择的站点位置有关去A是2p去B是2(x-p)。所以对于一辆车选择不同站点它每天的总成本是2 * a * p 2 * b * (x - p)。这里就产生了一个关键的“偏好”如果一辆车去A的次数远多于去B的次数即a很大b很小那么它肯定倾向于选一个p很小的站点因为这样去A的路程短反之如果它主要跑B市就会想选一个p很大的站点靠近B市。问题的难点在于站点资源容量c是有限的我们必须在全局上做出最优的分配。2. 核心思路与贪心策略解析2.1 问题转化与成本计算首先我们把总路程的公式写清楚。假设第i辆货车被分配到了第j个站点位置为p_j那么它每天行驶的总路程cost_i为cost_i 2 * a_i * p_j 2 * b_i * (x - p_j)这个公式可以展开并重新组合一下cost_i 2 * [a_i * p_j b_i * x - b_i * p_j] 2 * [b_i * x (a_i - b_i) * p_j]注意看2 * b_i * x这一项对于第i辆车来说是个常数无论它分配到哪个站点这部分成本都是固定的。真正影响分配决策的变量部分是2 * (a_i - b_i) * p_j。也就是说一辆车的“偏好”完全由它的差值d_i a_i - b_i决定。如果d_i 0说明这辆车去A市的次数多于去B市(a_i - b_i) * p_j是正的。为了最小化这部分成本我们希望p_j尽可能小。如果d_i 0说明这辆车主要跑B市(a_i - b_i)是负数乘以p_j后p_j越大反而能让这个负值变得更小因为负数乘以更大的正数结果更负从而降低总成本。所以它希望p_j尽可能大。如果d_i 0说明去A和去B的次数一样多那么(a_i - b_i) * p_j恒为0这辆车分配到哪里成本都一样只贡献固定的2 * b_i * x。因此我们的优化目标简化为将所有货车按照d_i的值进行分类和排序然后将d_i大的车需要小p分配给位置p小的站点将d_i小的车需要大p分配给位置p大的站点。2.2 贪心策略的可行性证明为什么这样做是全局最优的这里可以用交换论证的思想简单说明一下。假设在一个最优解中存在两辆车i和j以及两个站点S和T。车i的d_i值大于车j的d_i值但车i被分配到了位置p_T更大的站点T而车j被分配到了位置p_S更小的站点Sp_S p_T。让我们计算一下交换这两辆车的分配站点后的成本变化。交换前两辆车贡献的可变成本部分和为d_i * p_T d_j * p_S交换后可变成本和变为d_i * p_S d_j * p_T变化量 (d_i * p_S d_j * p_T) - (d_i * p_T d_j * p_S) (d_i - d_j) * (p_S - p_T)已知d_i d_j且p_S p_T所以(d_i - d_j) 0,(p_S - p_T) 0乘积为负数。这意味着交换后总成本降低了与“原方案是最优解”矛盾。因此在最优解中d值更大的车一定不会比d值更小的车分配到位置更大的站点。这正好印证了我们的贪心策略按d值降序排列的车应该匹配按p值升序排列的站点对于d0的车反之按d值升序排列的车即d值小或为负应该匹配按p值降序排列的站点。2.3 算法流程设计基于以上分析我们可以设计出清晰的算法步骤数据输入与存储读入n, m, x以及n个站点的(p, c)和m辆车的(a, b)。预处理货车数据计算每辆车的差值d a - b。这里有一个关键点题目中a和b的范围很大最大10^5d的范围是[-10^5, 10^5]而p最大可达10^8两者相乘可能达到10^13再乘以2最终答案可能超过int的表示范围约2e9。所以必须使用long long类型来存储答案和中间计算结果这是第一个容易踩的坑。排序策略将站点按位置p升序排序。将货车按差值d的绝对值|d|降序排序等等这里需要仔细推敲。我们之前说d值大的车偏好小pd值小的车偏好大p。如果直接按d值降序排那么d值最大正得最多的车排在最前面它应该去拿最小的pd值最小负得最多的车排在最后面它应该去拿最大的p。这听起来是对的。但是对于d值为正和负的车我们处理的方向是相反的。一个更清晰的实现方式是将d 0的车和d 0的车分开处理。实际上观察最终的成本公式2 * [b*x (a-b)*p]对于d 0的车我们希望p小对于d 0的车我们希望p大。d 0的车可以任意安排成本固定。因此我们可以将所有d 0的车按d值降序排列然后尝试分配给按p升序排列的站点从最小的站点开始用。同理将所有d 0的车按d值升序排列也就是按d的绝对值降序排列因为d是负数然后尝试分配给按p降序排列的站点从最大的站点开始用。贪心分配与累加答案维护两个指针或索引left指向当前可用的、位置最小的站点right指向当前可用的、位置最大的站点。遍历排序后的d 0的车队对于每辆车检查当前left指向的站点是否还有容量c 0。如果有就将这辆车分配到这个站点计算成本2 * (b*x d * p_left)累加到总答案中并将该站点的容量减1。如果该站点容量耗尽则将left指针向右移动指向下一个位置稍大的站点。遍历排序后的d 0的车队对于每辆车检查当前right指向的站点是否还有容量。如果有就分配计算成本2 * (b*x d * p_right)累加站点容量减1。容量耗尽则right指针向左移动。d 0的车它们的成本恒为2 * b * x与站点无关。可以在任意有容量的站点分配对总答案的贡献是固定的可以单独提前计算并累加。输出结果输出累加得到的总路程。注意题目保证所有站点容量总和Σc m所以我们的贪心分配过程一定能够完成不会出现车分不完的情况。3. C代码实现与逐行解析理解了算法我们来看C代码如何实现。下面是我参考并优化后的代码附上了详细的注释。#include bits/stdc.h using namespace std; // 使用long long防止数据溢出 typedef long long ll; // 定义站点结构体 struct Station { ll pos; // 站点位置 p ll cap; // 站点容量 c }; // 定义货车结构体或任务结构体 struct Truck { ll a, b; // 去A市和B市的次数 ll d; // 差值 d a - b }; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n, m, x; cin n m x; vectorStation stations(n); for (int i 0; i n; i) { cin stations[i].pos stations[i].cap; } vectorTruck trucks(m); // 用于分别存储 d0, d0, d0 的货车索引或任务 vectorTruck posD; // d 0 的车 vectorTruck negD; // d 0 的车 ll zeroCost 0; // 用于累加 d0 的车的固定成本 for (int i 0; i m; i) { cin trucks[i].a trucks[i].b; trucks[i].d trucks[i].a - trucks[i].b; if (trucks[i].d 0) { posD.push_back(trucks[i]); } else if (trucks[i].d 0) { negD.push_back(trucks[i]); } else { // d 0, 成本固定为 2 * b * x zeroCost 2 * trucks[i].b * x; } } // 1. 对站点进行排序 // d0的车需要小p所以站点按pos升序排 sort(stations.begin(), stations.end(), [](const Station s1, const Station s2) { return s1.pos s2.pos; }); // 2. 对货车任务进行排序 // d0的车按d值降序排最需要小p的车排前面 sort(posD.begin(), posD.end(), [](const Truck t1, const Truck t2) { return t1.d t2.d; // 降序 }); // d0的车按d值升序排即按绝对值降序最需要大p的车排前面 sort(negD.begin(), negD.end(), [](const Truck t1, const Truck t2) { return t1.d t2.d; // 升序因为d是负数 }); ll totalCost zeroCost; // 总成本初始化为d0的车的成本 int idxLeft 0; // 指向当前可用最小站点的指针 int idxRight n - 1; // 指向当前可用最大站点的指针 // 3. 分配 d 0 的车队 for (const auto truck : posD) { // 找到还有容量的最小位置站点 while (idxLeft n stations[idxLeft].cap 0) { idxLeft; } // 根据题目保证这里一定能找到站点 ll cost 2 * (truck.b * x truck.d * stations[idxLeft].pos); totalCost cost; stations[idxLeft].cap--; // 占用该站点一个容量 } // 4. 分配 d 0 的车队 for (const auto truck : negD) { // 找到还有容量的最大位置站点 while (idxRight 0 stations[idxRight].cap 0) { idxRight--; } // 根据题目保证这里一定能找到站点 ll cost 2 * (truck.b * x truck.d * stations[idxRight].pos); totalCost cost; stations[idxRight].cap--; // 占用该站点一个容量 } cout totalCost endl; return 0; }代码关键点解析数据结构选择使用vector存储站点和货车信息比原生数组更安全方便。定义了Station和Truck结构体让数据更清晰。输入输出优化ios::sync_with_stdio(false);和cin.tie(0);是ACM/信奥竞赛中常见的关闭同步流、解绑cin/cout的语句能显著加快大量数据读入的速度。分类处理将货车按d值分为正、负、零三类分别放入不同的vector。d0的车辆成本直接累加不参与后续的贪心分配简化了逻辑。排序逻辑站点按pos升序排序这是为了便于d0的车从小到大取用。d0的车按d降序排序让d值最大的车最“渴望”小p的车最先挑选。d0的车按d升序排序因为d是负数升序排序意味着绝对值大的也就是更负的排在前面它们最“渴望”大p。双指针分配idxLeft和idxRight是两个指针分别从排序后的站点数组的两端向中间移动。d0的车消费左侧小p站点的容量d0的车消费右侧大p站点的容量。使用while循环跳过容量已耗尽的站点确保每次分配时指针指向的站点一定有可用容量。成本计算严格按照推导出的公式2 * (b*x d*p)计算每辆车的成本并累加。注意整个计算过程使用long long。4. 算法正确性验证与样例分析让我们用题目给的样例来手动验证一下算法的正确性。样例输入3 4 10 1 1 2 1 8 3 5 3 7 2 9 0 1 10000步骤拆解读入数据n3, m4, x10站点S1(pos1, cap1), S2(pos2, cap1), S3(pos8, cap3)货车T1(a5,b3), T2(a7,b2), T3(a9,b0), T4(a1,b10000)计算差值d并分类T1: d 5-3 2 0 - 归入posDT2: d 7-2 5 0 - 归入posDT3: d 9-0 9 0 - 归入posDT4: d 1-10000 -9999 0 - 归入negD没有 d0 的车所以zeroCost 0。排序站点已按pos升序排好[S1(1,1), S2(2,1), S3(8,3)]。posD内的车按d降序排[T3(d9), T2(d5), T1(d2)]。negD内的车只有T4(d-9999)按升序排就是它自己。贪心分配处理posD(需要小p)当前idxLeft0指向S1(1,1)。处理T3(d9)成本2*(0*10 9*1)18总成本18。S1容量减为0。idxLeft移动到1指向S2(2,1)。处理T2(d5)成本2*(2*10 5*2)2*(2010)60总成本78。S2容量减为0。idxLeft移动到2指向S3(8,3)。处理T1(d2)成本2*(3*10 2*8)2*(3016)92总成本170。S3容量减为2。处理negD(需要大p)当前idxRight2指向S3(8,2)。处理T4(d-9999)成本2*(10000*10 (-9999)*8)2*(100000 - 79992)2*2000840016。总成本 170 40016 40186。S3容量减为1。输出40186与样例输出一致。这个分配方案T3-S1, T2-S2, T1-S3, T4-S3也正是题目说明中给出的最优解。可以看到d值最大的T3最需要小p分配到了最小的站点p1d值为负且绝对值巨大的T4最需要大p分配到了最大的站点p8中间的车则匹配了剩余的站点。我们的算法完美地复现了这个最优分配。5. 性能分析与优化要点这道题的数据范围是n, m ≤ 10^5所以算法的时间复杂度必须控制在O(n log n)或O(m log m)级别。时间复杂度算法的耗时主要在于排序。对站点排序O(n log n)对posD和negD排序总规模为m所以是O(m log m)。后续的贪心分配是线性的O(m)。因此总复杂度为O((nm) log (nm))在10^5的数据量下完全可行。空间复杂度我们使用了vector存储站点和货车信息空间为O(nm)。几个关键的优化和注意事项使用long long这是本题最容易犯的错误。a, b, p, x都在10^5量级a*x或b*x可能达到10^10再乘以2仍在long long范围内。但如果在中间计算时使用了int可能会导致溢出得到错误结果。所有与成本计算相关的变量包括循环变量i最好都声明为long long以避免隐式类型转换带来的风险。输入输出效率面对10^5级别的数据读入使用cin/cout而不优化可能会超时。务必加上ios::sync_with_stdio(false); cin.tie(0);。如果还担心可以用C风格的scanf/printf但要注意long long的格式符是%lld。避免不必要的复制在排序和遍历时如果结构体较大可以考虑存储索引而非整个结构体或者使用移动语义。不过本题数据量下直接操作结构体vector完全可以接受。指针移动的边界检查在while循环中移动idxLeft和idxRight时要确保索引不越界 (idxLeft n,idxRight 0)。虽然题目保证容量足够但良好的编程习惯能避免潜在的崩溃。6. 常见错误与调试技巧在实现和调试这道题时我遇到过也看到别人常犯的一些错误整数溢出这是最大的坑。表现是样例能过但提交后部分测试点错误尤其是后面的大数据点。检查所有变量类型特别是ans,cost以及a*x,b*x,d*p这些乘积项必须用long long。排序逻辑错误错误地将所有车按|d|降序排序然后统一分配。这忽略了d的正负号决定的偏好方向要小p还是要大p。必须将正负车队分开处理。对于d0的车队错误地也按d降序排。因为d是负数降序排列会把绝对值小的比如-1排在绝对值大的比如-100前面这不符合“最需要大p的车优先”的原则。应该按d升序排。站点容量更新与指针移动在分配车辆并减少站点容量后如果容量变为0指针必须移动到下一个可用站点。这个逻辑要写在循环里确保每次为新车分配时指针指向的站点一定是可用的。我最初的版本是在分配后才检查容量并移动指针导致下一辆车可能仍试图使用容量为0的站点。忽略 d0 的情况d0的车成本固定可以提前计算。如果混入贪心分配流程虽然不影响最终结果因为d0乘p等于0但可能会浪费代码判断或者影响站点指针的位置。单独处理它们逻辑更清晰。输出忘记乘以2成本公式里有个系数2容易在累加时遗漏。务必在最终计算cost时乘以2或者在最后输出totalCost * 2。调试建议先小规模验证自己构造几个小的测试用例比如2个站点2辆车手动计算最优解然后看程序输出是否一致。打印中间变量在本地调试时可以打印出排序后的车队d值序列、站点p值序列以及分配过程中每辆车的分配站点和计算出的成本与手动模拟的过程对比。边界测试考虑极端情况比如所有车的d都为正、所有车的d都为负、所有站点容量都为1、x很大、p值很密集等检验程序的鲁棒性。7. 总结与举一反三“运送物资”这道题是一个包装得很好的贪心算法应用题。它成功地将一个看似复杂的调度问题转化为了一个清晰的排序匹配问题。其核心洞察在于发现每辆车的成本可以分解为一个固定项和一个与站点位置相关的可变项而这个可变项的影响因子就是(a-b)。一旦抓住了这个关键问题的解决路径就豁然开朗了。这类问题的通用解题思路是形式化目标函数将总代价明确地写出来。分解与提取尝试将目标函数分解为与每个独立个体这里是每辆车相关的部分并进一步分离出常数项和与选择相关的变量项。分析偏好针对每个个体分析其变量项在不同选择下的变化趋势确定其“偏好”例如喜欢大的还是小的参数。排序与贪心匹配根据个体的“偏好”对个体进行排序根据资源站点的特性对资源进行排序然后按照“最渴望的个体优先获得最合适的资源”的原则进行匹配。验证贪心选择性通常可以通过交换论证来证明贪心策略的正确性。在信奥和算法竞赛中类似的贪心题目还有很多例如“排队接水”、“线段覆盖”、“活动安排”等其本质都是通过排序来获得最优的局部选择顺序。多练习这类题目能够很好地锻炼对问题本质的抽象能力和对贪心策略的敏感度。最后对于C实现除了算法本身还要时刻注意数据范围开long long、输入输出效率、代码清晰度等工程细节。把这些都做到位才能在竞赛中稳定地拿到满分。