1. 项目概述KOI竞赛中的“鹅卵石”问题最近在带学生准备信息学奥林匹克竞赛OI和KOI这类国际赛事时我发现很多同学对“模拟”和“贪心”类题目的结合感到棘手。正好刷到了KOI 2022第一轮的这道P12687“鹅卵石”题觉得它是个非常经典的案例。这道题表面上看是简单的搬运模拟但里面嵌套的贪心选择策略恰恰是区分普通选手和高手的关键。很多孩子一看到题目描述里“从左到右”、“每次搬最左边能搬的”就觉得直接模拟就行结果一写就超时或者漏掉了关键情况。今天我就结合自己十多年打比赛和教学的经验把这道题的核心思路、完整实现、以及那些容易踩的坑掰开揉碎了讲清楚。无论你是正在备赛的信奥生还是想提升C算法能力的开发者相信这篇从实战角度的解析都能让你有所收获。简单来说这道题描述了一个这样的场景你面前有一条无限长的路路上某些整数坐标位置放着鹅卵石。你有一个容量为 K 的背包从坐标0出发目标是收集所有鹅卵石并带回原点坐标0。你每次只能搬动背包容量范围内的石头并且移动速度是每单位距离花费1单位时间。题目要求我们计算完成所有收集任务的最短时间。这本质上是一个带有容量限制的往返运输优化问题非常考验对问题模型的抽象能力和策略选择。2. 问题核心与思路拆解为什么不能蛮干拿到题目尤其是信奥/IOI系列的题目第一步永远不是急着敲代码而是彻底理解数据范围和问题本质。我们先看题目给出的关键约束鹅卵石的数量 N 最大可以达到 10^5坐标的绝对值最大也能到 10^9。这个数据范围直接宣告了任何 O(N^2) 或更高复杂度的算法都是死刑必须寻找 O(N log N) 或线性的解法。2.1 关键观察与贪心策略证明为什么最直观的“每次搬最左边能搬的”模拟会出问题我们设想一个场景石头位置在 [-100, 1, 2]背包容量 K2。如果严格从左到右搬顺序是去-100搬两块-100和1回0再去2搬一块回0。总路程是 (100 100) (2 2) 204。但最优策略呢先去右边搬1和2回0再去左边搬-100回0。总路程是 (2 2) (100 100) 204等等算出来一样别急我们再看一个例子石头在[-10, -9, 100] K2。严格从左到右搬-10和-9路程20再去100搬一块路程200总220。最优策略单独去100搬一块路程200再去左边搬-10和-9路程20总220看起来还是没区别。这里就引出了第一个核心洞察对于原点同一侧的石头最优搬运顺序就是由远及近地搬运。因为这样可以在回来的路上“顺便”带上更近的石头减少空跑。但问题真正的难点和贪心策略体现在如何分配背包容量给原点左右两侧的石头。让我们形式化地思考。假设原点左侧的石头位置是 L1, L2, ... Lp (都是负数我们取绝对值处理记为left[])并按距离从大到小排序。右侧同理R1, R2, ... Rq (正数right[])。搬运一侧的所有石头所需的最短时间是2 * sum_of_distances。但这只是在背包容量无限大的情况下。当背包容量 K 有限时我们可能需要往返多次。对于一侧比如左侧的石头如果最远的石头距离是 D那么至少需要ceil(count_left / K)趟来完成。每一趟我们都尽可能装满 K 个石头并且从最远的还没搬的开始搬。这样这一侧的总耗时就是2 * (最远距离 次远距离 ...)。但更精确的计算是我们把这一侧的石头按距离从大到小分组每组K个最后一组可能不足K个。那么总时间就是2 * (第一组最远石头距离 第二组最远石头距离 ...)。那么左右两侧该如何交叉进行呢这就是本题贪心的精髓所在。一个错误的思路是先完全搬完一侧再搬另一侧。考虑这个例子left [100], right [1, 2], K2。如果先搬完左侧耗时200再搬右侧耗时4总204。但如果我们先去右侧搬1和2耗时4再去左侧搬100耗时200总时间还是204没差。但如果left[100], right[90, 91], K2呢先左后右200 182 382。先右后左182 200 382。依然一样我们需要一个能产生差异的例子。关键在于最后一趟想象一下如果你在完成所有搬运任务的最后一趟你的背包可能没有装满。如果你最后一趟是去较远的那一侧那么你回来的路程是满载的但去的时候是空载。但如果你能安排最后一趟是去较近的那一侧并且这一趟能“顺便”结束任务那么去和回的路程利用率可能不同吗实际上在经典的“搬石头”或“送快递”模型里有一个重要的结论总时间等于2 * 所有石头到原点的距离之和减去最后一趟可以节省的距离。而这个“可以节省的距离”就是最后一趟的目的地最远的那块石头所在的位置的距离。因为最后一趟你去了那里拿了石头然后回来但任务结束了你不需要再返回原点进行下一趟。所以最后一趟的“回程”从某种意义上说不是必须的不你仍然需要回到原点。但是你可以选择让哪一趟成为“最后一趟”。最优策略就是让距离原点最远的那块石头在它被搬运的那一趟成为整个任务的最后一趟。这样你在计算总往返次数时对于这个最远的点你只需要计算“去”的距离而不用计算“回”的距离不对你仍然需要回来。这里常见的贪心策略是总时间 2 * 所有石头距离之和 - 最远石头的距离。但这个公式成立的前提是你可以安排最远的石头在最后一趟被搬运并且那一趟只搬它一块石头或者说不影响其他石头的搬运计划。当有容量限制K时情况更复杂。经过分析并结合KOI官方题解常见的思路本题的正确贪心策略是将石头按位置分为左侧负和右侧正并分别按距离原点的绝对值从大到小排序。对于每一侧我们独立计算如果只搬运这一侧的石头需要的时间。计算方式是将该侧石头按距离排序后每次取最远的K个或不足K个作为一组该组的耗时是2 * 该组中最远石头的距离。将所有组的耗时相加。但是整个任务的总时间并不是time_left time_right。因为可能存在“节省一趟”的机会。想象一下如果你要去左边搬一组石头最远距离是L也要去右边搬一组石头最远距离是R。如果 L R那么你可以把去左边最远的那一趟安排为整个任务的最后一趟。在这一趟里你去了距离L的地方搬了石头然后回来。但任务就此结束。然而你去右边搬最远距离R的那一趟仍然需要一次完整的往返2R。所以总时间似乎是(2*L 2*R) - L L 2R这不对因为左边的其他组如果不是最远组也需要时间。实际上更通用的最优解是总时间 左侧所需时间 右侧所需时间 - max(最左侧组距离 最右侧组距离)。这里的“最左/右侧组距离”指的是各自方向排序后第一组即包含最远石头的那一组中最远石头的距离。为什么可以减因为整个任务的最后一趟必然是去某个方向搬运一组石头。这一趟的“返程”虽然发生但任务在返程到达原点时就结束了所以这一趟的“返程”时间不能像中间趟那样为后续趟服务。但从计算上看我们之前计算每一侧时间时每一趟都计算了2*distance。如果最后一趟是去距离为D的方向那么这一趟我们多算了一个D因为返程后任务结束这个返程不应该被看作是为后续搬运做准备的成本。因此我们可以减去这个D。为了最大化节省我们选择减去max(左侧最远组距离, 右侧最远组距离)。注意这个策略的理解需要仔细体会“最后一趟”的意义。在模拟计算中我们通常假设每一趟都是完整的往返。但全局来看最后一趟的返程是任务的终点不像中间趟的返程是下一趟的起点。因此总时间可以理解为所有完整往返时间之和再减去最后一趟的“返程”距离。而这个返程距离就是最后一趟目的地即某一侧最远组的距离。2.2 算法流程设计基于以上分析我们可以设计出清晰的算法步骤数据读取与分组读取石头数量N、容量K以及每个石头的位置。将位置小于0的放入left数组并取其绝对值方便计算距离将位置大于0的放入right数组。位置等于0的石头可以忽略因为已经在原点。排序将left和right数组分别按降序排序从最远到最近。计算单侧时间函数设计一个函数calculateTime(vectorint stones, int k)输入一个已排序的石头距离数组和容量K返回搬运完这一侧所有石头所需的时间。初始化时间time 0。从最远的石头开始数组下标i 0每次处理一组最多K个。这一组的耗时是2 * stones[i]因为stones[i]是这一组里最远的。然后将索引i增加 K处理下一组。循环直到处理完所有石头。计算双侧时间并应用贪心计算total_time calculateTime(left, K) calculateTime(right, K)。找出左侧最远石头的距离如果left非空则为left[0]否则为0记为maxLeft。找出右侧最远石头的距离如果right非空则为right[0]否则为0记为maxRight。最终答案ans total_time - max(maxLeft, maxRight)。输出结果。这个算法的时间复杂度是 O(N log N)主要来自排序后续计算是线性的完全满足题目要求。3. C实现与代码逐行精讲思路清晰了接下来我们用C实现。我会用标准库和清晰的代码风格并加上详细注释。#include iostream #include vector #include algorithm #include cmath using namespace std; // 计算搬运一侧石头所需的时间 // stones: 该侧石头到原点的距离数组已按降序排序从远到近 // k: 背包容量 long long calculateTime(vectorint stones, int k) { long long time 0; int n stones.size(); // 从最远的石头开始每次处理最多k个 for (int i 0; i n; i k) { // 这一组中最远的石头距离是 stones[i] // 一趟往返需要 2 * distance time 2LL * stones[i]; } return time; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, K; cin N K; vectorint left, right; for (int i 0; i N; i) { int position; cin position; if (position 0) { // 左侧石头存储其绝对距离 left.push_back(-position); } else if (position 0) { // 右侧石头直接存储距离 right.push_back(position); } // position 0 的石头在原点忽略 } // 降序排序最远的石头在前 sort(left.begin(), left.end(), greaterint()); sort(right.begin(), right.end(), greaterint()); // 计算两侧各自所需时间 long long totalTime calculateTime(left, K) calculateTime(right, K); // 找出两侧最远石头的距离 int maxLeftDist left.empty() ? 0 : left[0]; int maxRightDist right.empty() ? 0 : right[0]; // 总时间减去最远的那一趟的返程距离 long long ans totalTime - max(maxLeftDist, maxRightDist); cout ans endl; return 0; }现在我们来逐段解析关键代码和易错点第一部分头文件与工具函数#include iostream #include vector #include algorithm #include cmath using namespace std;这是标准配置。cmath在这里其实用不到abs因为我们手动处理了负数但留着也无妨。使用using namespace std;在竞赛中很常见可以节省时间但在大型工程项目中应避免。第二部分calculateTime函数这是核心函数。注意几个细节long long类型这是本题最关键的数据类型选择石头坐标绝对值最大10^9搬运次数最多10^5那么总时间最大可能超过2 * 10^9 * 10^5 2e14这远远超出了int约21亿的表示范围。必须使用long long在大多数评测系统上是64位整数。我在函数内部time 2LL * stones[i];这里用了2LL而不是2目的是确保乘法运算在long long类型下进行避免int溢出。循环for (int i 0; i n; i k)这里实现了分组。i每次指向一组中最远的那个石头。因为数组是降序的所以stones[i]就是这组石头中最远的距离。这种跳跃式遍历是O(N/K)的效率很高。为什么是2 * distance因为每一趟都是去-回一个完整的往返。即使最后一组石头离原点很近你从原点出发去拿它们也必须回到原点虽然任务可能就此结束但在计算单侧时间时我们暂不考虑全局最后一趟的优化。第三部分主函数main中的数据处理ios::sync_with_stdio(false); cin.tie(nullptr);这是C竞赛中经典的输入输出加速语句。关闭C标准流与C标准流的同步并解除cin与cout的绑定可以大幅提升大量数据读写的速度。几乎成了竞赛代码的标配。分组存储我们将左侧石头距离存为正值-position右侧石头直接存position。这样两边的距离都是非负整数便于统一处理。排序sort(left.begin(), left.end(), greaterint())实现了降序排序。greaterint()是一个函数对象表示“大于”比较从而让大的元素排在前面。处理空数组在计算maxLeftDist和maxRightDist时必须判断数组是否为空。如果为空则最远距离视为0。因为如果一侧没有石头那么“最远距离”不应该参与最终的减法计算或者说减去0不影响结果。第四部分最终计算与输出long long ans totalTime - max(maxLeftDist, maxRightDist);这就是贪心策略的最终体现。totalTime是假设所有趟都是完整往返的总时间。max(maxLeftDist, maxRightDist)是全局最远的那组石头的距离。我们减去它相当于将去往这个最远点的那一趟视为任务的最后一趟从而节省了从该点返回原点的“返程”时间因为我们在计算该侧时间时已经为这一趟计算了2*distance包含了往返但实际上最后一趟的返程结束后任务就完结了不需要再为后续服务所以可以省掉一个单程的距离。4. 测试与边界情况分析任何算法代码不经测试就是耍流氓。我们构造几组测试数据验证代码的正确性和鲁棒性。测试用例1基础功能输入 3 2 -5 3 7左侧石头[5]右侧石头[7, 3]排序后为[7, 3]。左侧时间2 * 5 10右侧时间第一组[7](i0):2*714 第二组[3](i2 已越界实际循环只执行一次等等这里右侧有两个石头K2。排序后是[7,3]。循环i0处理stones[0]7这一组包含了stones[0]和stones[1]因为K2所以时间加上2*714。然后i2后i2不小于n2循环结束。所以右侧时间是14。totalTime 10 14 24maxLeftDist 5,maxRightDist 7ans 24 - max(5,7) 24 - 7 17手动模拟验证最优策略可能是先去右边搬7和3耗时7714因为去7回0再去左边搬5耗时5510总24。但根据我们的公式最后一趟如果是去右边搬7最远点那么这一趟的返程7可以节省等等我们算的总时间是24减去7得17。这个17怎么来的如果我们把去右边搬7和3的那一趟作为最后一趟先去左边搬5往返10再去右边搬7和3单程7因为搬到3和7后回到原点任务结束但回程还是发生了。总时间 10 7 17。确实因为最后一趟去右边我们只需要计算“去”的距离7而不用计算“回”的距离7因为任务在返回原点后结束。但注意在这一趟里我们也搬了3号石头它离原点更近但这不影响最远距离是7。所以答案是17正确。测试用例2容量为1的特殊情况输入 4 1 -10 -20 5 15左侧[20, 10]右侧[15, 5]。左侧时间2*20 2*10 60右侧时间2*15 2*5 40totalTime 100maxDist max(20,15) 20ans 100 - 20 80手动模拟每次只能搬一块。最优顺序肯定是先搬完一侧吗不一定。但根据我们的公式总时间等于所有石头距离之和的两倍再减去最远石头的距离2*(2010155) - 20 2*50 -20 80。可以验证无论按什么顺序只要保证搬运最远石头20的那一趟是最后一趟总时间就是80。如果先搬20再搬其他时间会更长。所以算法正确。测试用例3一侧无石头输入 2 3 5 8左侧为空右侧[8, 5]。左侧时间0右侧时间K3一次可搬完。时间2*816因为最远是8totalTime 16maxLeftDist 0,maxRightDist 8ans 16 - 8 8验证只有右侧石头一趟搬完8和5最远距离8。总时间就是一趟往返2*816减去最后一趟的返程距离8得到8。实际上任务就是去8的地方沿途拿了5再回到0。花费的时间是8去 8回16但为什么答案是8这里出现了理解偏差。注意当只有一侧有石头时我们的公式totalTime - maxDist还正确吗totalTime我们算的是16maxDist8ans8。但实际最少时间是多少我们去到8沿途拿5再回来。总路程是8去最远点 8回来 16。不可能为8。所以我们的计算出了问题。停下来这是一个非常重要的边界情况也是很多初学者甚至一些老手容易忽略的点我们重新审视公式总时间 左侧时间 右侧时间 - max(左侧最远, 右侧最远)。这个公式的推导基于一个假设最后一趟的返程可以节省。但是当只有一侧有石头时“最后一趟”就是搬运这一侧石头的唯一一趟或最后一组。在这一趟中你确实需要从最远点返回原点。这个返程是无法节省的因为任务在你返回原点后才结束。公式中“减去最远距离”意味着我们省去了返程但实际返程是发生的。那么问题出在哪里关键在于我们对calculateTime函数的定义。在这个函数里我们计算某一侧时间时已经包含了从该侧最远点返回原点的“返程”。但在全局视角下如果整个任务只有一侧有石头那么任务的最后一趟就是搬运这一侧的最后一组这一趟的返程是实际发生的不能省。因此我们的贪心策略修正如下总时间 左侧时间 右侧时间 - max(左侧最远组距离, 右侧最远组距离)但这个公式仅在两侧都有石头时成立。如果只有一侧有石头那么总时间就等于这一侧的时间不能减。所以我们需要修改最终的计算逻辑long long ans totalTime; if (!left.empty() !right.empty()) { ans - max(maxLeftDist, maxRightDist); }或者更简洁地long long ans totalTime; int maxDist 0; if (!left.empty()) maxDist max(maxDist, left[0]); if (!right.empty()) maxDist max(maxDist, right[0]); // 如果maxDist不为0且它对应的那一侧在计算time时被计入了2倍我们需要减去一倍。 // 但注意totalTime里已经包含了所有组的2倍距离。 // 正确的减法应该是只有当两侧都有石头时才能减去一个最远距离。 // 因为如果只有一侧减去后相当于只计算了单程这是错误的。 if (!left.empty() !right.empty()) { ans - maxDist; }让我们用修正后的逻辑重新计算测试用例3totalTime 16因为右侧非空左侧空所以不执行减法。ans 16。正确再验证一下测试用例1两侧都有石头totalTime 24,maxDist 7, 两侧非空ans 24-717。正确。测试用例4石头就在原点输入 3 2 0 -1 2根据我们的代码位置0的石头被忽略。左侧[1]右侧[2]。左侧时间2*12右侧时间2*24totalTime6两侧非空maxDist max(1,2)2ans 6-24手动模拟先搬右侧2往返4再搬左侧1往返2总6。但如果我们先去左侧搬1往返2再去右侧搬2单程2因为最后一趟总时间224。正确。原点上的石头不影响计算。测试用例5大容量一次搬完输入 5 100 -1000 -500 30 600 1200左侧[1000, 500]右侧[1200, 600, 30]。 排序后左侧[1000,500]右侧[1200,600,30]。左侧时间K100 2所以一组搬完时间2*10002000右侧时间一组搬完时间2*12002400totalTime4400两侧非空maxDist max(1000,1200)1200ans 4400-12003200验证最优策略就是一趟搞定所有。去最远点1200沿途收集所有石头返回。总路程 1200去 1200回 2400等等这里左侧有石头在-1000和-500。如果从0出发去1200无法途径-1000。所以一趟无法收集所有石头。实际上我们需要至少两趟一趟去右边一趟去左边。那么最优顺序先去右边1200搬回再去左边1000搬回。时间 2*1200 2*1000 4400。如果我们把去右边1200作为最后一趟那么时间 2*1000 1200 3200。看来我们的算法结果是3200这是正确的。因为去左边1000是完整往返2000去右边1200是最后一趟只需单程1200。总3200。经过以上测试和修正我们得到了一个健壮的算法。修正后的核心计算部分如下long long totalTime calculateTime(left, K) calculateTime(right, K); long long ans totalTime; // 贪心优化如果两侧都有石头最后一趟的返程可以省去 // 省去的距离是两侧最远距离中的最大值 if (!left.empty() !right.empty()) { int maxLeftDist left[0]; // 已经排序第一个就是最大 int maxRightDist right[0]; ans - max(maxLeftDist, maxRightDist); } // 如果只有一侧有石头则 totalTime 就是答案无需减去 cout ans endl;5. 常见错误与实战调试技巧即便思路和代码都清晰了在竞赛环境中依然可能因为各种细节功亏一篑。下面我总结几个常见的“坑”和调试技巧。5.1 数据类型与溢出这是信奥题目中最常见的错误之一本题也不例外。错误示例使用int类型存储totalTime或ans。单个距离最大10^9搬运次数可达10^5总时间可能达到2e14远超int的约21亿2e9范围。正确做法所有与总时间相关的变量totalTime,ans,calculateTime返回值及其内部累加变量都必须使用long long。在C中long long至少是64位范围大约在±9e18足够安全。乘法溢出即使在long long变量中如果运算中间量是int也可能溢出。例如time 2 * stones[i];如果stones[i]是int且值大于10^9那么2 * stones[i]这个表达式会先以int类型计算可能溢出然后再赋值给long long的time为时已晚。所以必须写time 2LL * stones[i];让2LL这个long long字面量强制提升整个表达式到long long类型计算。5.2 排序顺序与分组逻辑排序方向我们必须按距离从大到小排序降序。如果升序排序那么stones[0]就是最近的石头分组逻辑就完全错了会导致计算结果偏小因为你用最近石头的距离代表整组的耗时。分组索引跳跃循环for (int i 0; i n; i K)确保了每组从当前最远的未处理石头开始。这里i的增量是K而不是1。一定要理解i指向的是每一组“领头”的石头该组最远的组内其他石头索引i1到iK-1虽然也被这一趟搬运但它们的距离不影响该趟的耗时耗时由最远的决定。5.3 边界条件处理空数组处理在计算maxLeftDist和maxRightDist时必须检查left.empty()和right.empty()。直接访问left[0]或right[0]在向量为空时会导致未定义行为运行时错误。只有一侧有石头如上文详细分析的这是最易错的贪心边界。当只有一侧有石头时不能应用减去最远距离的优化。我们的代码通过if (!left.empty() !right.empty())条件进行了保护。K大于石头数量我们的分组逻辑依然有效。例如一侧有2个石头K10那么for (int i0; i2; i10)只会执行一次i0stones[0]就是最远石头正确计算出一趟的时间。所有石头都在原点题目未明确说明但根据逻辑位置为0的石头无需搬运时间应为0。我们的代码会将其忽略left和right都为空totalTime0条件判断不执行减法ans0正确。5.4 输入输出与性能输入输出加速在C中对于超过10^5量级的输入使用cin/cout而不加速可能会超时。务必加上ios::sync_with_stdio(false); cin.tie(nullptr);。注意加了这两句后就不要混用scanf/printf和cin/cout了。避免不必要的拷贝calculateTime函数参数使用vectorint引用传递避免复制整个数组。5.5 调试与测试方法在平时练习时不要只依赖样例。构造小数据手工计算一些N很小比如3到5的情况验证程序输出。构造对称数据比如左右各一个石头距离相等容量为1或2检验结果是否符合直觉。构造极值数据N10^5所有石头都在最远点如10^9K1。检查程序是否运行超时或溢出。对拍写一个简单的暴力程序用于N很小的情况比如N10用随机数据生成器产生大量随机输入分别用你的优化程序和暴力程序计算对比结果是否一致。这是发现逻辑错误最有效的方法。6. 算法扩展与思维提升解决这道题不仅仅是为了AC更是为了训练一种思维模式。这种“带容量限制的往返运输”问题可以有很多变种。变种1起点和终点不同。如果不是回到原点而是要去另一个目的地。那么每一趟的路径就不再是简单的“原点-目标点-原点”计算方式需要调整。变种2多个人或多次运输。这实际上将问题引入了并行计算的领域可能会用到优先队列等数据结构来调度。变种3石头有重量背包有承重限制。这就变成了一个更复杂的背包问题与路径规划的结合。变种4动态插入石头。石头不是一开始全部给出而是在过程中出现。这可能需要在线算法或数据结构来维护当前的最优策略。对于信奥选手来说从这道题中可以提炼出更通用的解题框架分析问题模型识别出这是“运输优化”类问题核心成本是距离。寻找最优子结构发现对于同一侧的石头由远及近分组搬运是最优的。发现贪心选择性质全局最优解可以通过每次选择“最远点”所在的侧进行最后一趟运输来构造。处理边界情况仔细分析单侧、空集、容量为1等特殊情况。在代码实现上养成了使用long long防溢出、注意输入输出加速、严格处理边界条件的习惯这些细节在竞赛中往往决定着胜负。最后再分享一个我个人的调试心得当你觉得贪心策略想不明白的时候试着画图。在纸上画出数轴标出石头的位置用小圆圈代表背包容量手动模拟几次搬运过程。很多时候直观的图形能帮你发现那些纯逻辑思考容易漏掉的细节比如“最后一趟”的返程到底能不能省画个时间轴或者路径图就一目了然了。这道“鹅卵石”题就是KOI送给选手们的一份经典礼物它用不复杂的场景考察了选手对数据范围的敏感、对贪心策略的证明能力以及对边界情况的周密思考。