1. 项目概述与问题定义最近在刷算法题和准备面试的时候遇到了一个挺有意思的经典问题我把它叫做“补给站最优花费问题”。乍一看这像是一个模拟题或者简单的贪心但深入分析后发现它其实是一个考察动态规划思想尤其是“状态机DP”和“决策优化”的绝佳案例。很多朋友在初次接触时容易陷入“看到低价就买”的直觉陷阱结果写出来的代码要么超时要么答案不对。我自己在解决这个问题的过程中也踩了不少坑最终摸索出了一套清晰、高效且易于理解的C实现方案。简单来说这个问题描述了一个旅行者或者车辆沿着一条直线路径前进路径上分布着若干个补给站。每个补给站有两个关键信息距离起点的位置以及在该站购买单位补给比如汽油、食物的价格。旅行者有一个容量上限即最多能携带多少单位的补给。目标是从起点出发到达终点总路程消耗的补给量是固定的。我们需要规划在哪些补给站购买多少补给才能使得总花费最小。这本质上是一个在“空间”位置和“资源”补给量两个维度上的最优决策问题。这个问题之所以值得深究是因为它融合了贪心算法的局部最优思想和动态规划的全局面最优保证。你不能只看眼前哪个站便宜因为你的携带容量限制了你的“囤货”能力你也不能无脑地在最便宜的站买完所有东西因为你可能根本到不了那个站。它要求我们在行程的每一步都根据当前剩余的补给、未来的价格信息做出一个“瞻前顾后”的决策。接下来我就结合C实现把这个问题从问题分析、思路推导、代码实现到调试心得完整地梳理一遍。2. 核心思路与算法设计2.1 问题建模与关键约束首先我们需要把问题抽象成计算机能处理的数据模型。假设有n个补给站编号0到n-1其中第0个站是起点第n-1个站是终点。我们用一个数组dist[i]表示第i个站距离起点的距离用一个数组price[i]表示在第i个站购买单位补给的价格。注意终点可能也是一个补给站价格通常视为0或不购买也可能只是一个位置点。旅行者有一个最大携带容量C。假设每单位距离消耗1单位补给那么从站点i到站点i1的距离d dist[i1] - dist[i]就需要消耗d单位的补给。这里有一个隐含的可行性条件任意两站之间的距离必须小于等于容量C否则旅行者无法直接到达问题无解。我们在预处理时需要检查这一点。我们的决策变量是什么是在每个站点i 当到达时剩余油量fuel_left的情况下需要购买多少油量buy。目标是总花费最小。这立刻引导我们想到动态规划。2.2 动态规划状态设计最直接的状态设计是dp[i][f]表示到达第i个补给站并且此时剩余补给量为f时所花费的最小成本。其中i的范围是[0, n-1]f的范围是[0, C]。状态转移方程如何推导我们从状态dp[i][f]出发考虑在站点i的决策购买b单位补给0 b C - f因为购买后总量不能超过容量C。购买需要花费b * price[i]。购买后补给量变为f b。然后我们出发前往下一个站点i1消耗need dist[i1] - dist[i]的补给。因此到达站点i1时的剩余补给量应为f b - need。这个值必须非负。由此我们可以得到状态转移方程dp[i1][fb-need] min(dp[i1][fb-need], dp[i][f] b * price[i])其中b需要遍历所有可能的购买量。初始化dp[0][0] 0表示在起点剩余油量为0花费为0。其他状态初始化为无穷大INF。答案最终答案是dp[n-1][0]即到达终点时剩余油量为0的最小花费。如果终点不是补给站我们可能需要允许终点有非零剩余油量但通常问题会规定到达终点即可剩余油量不计。这里我们按严格消耗完来处理。这个DP思路是清晰的但存在一个效率问题状态数是O(n * C)对于每个状态我们需要枚举购买量b这又是O(C)的复杂度。总时间复杂度为O(n * C^2)。当C很大时比如10^4这个算法是不可接受的。我们需要优化。2.3 贪心优化与单调队列观察状态转移方程dp[i1][new_f] min(dp[i][f] b * price[i])其中new_f f b - need所以b new_f need - f。 我们可以把方程改写为dp[i1][new_f] min_{f} (dp[i][f] - f * price[i]) (new_f need) * price[i]其中f的取值范围需要满足0 f C且new_f need - f 0即b 0且new_f need - f C - f即b C - f化简后是关于f的一个窗口范围。对于固定的new_f和i我们需要在一个滑动窗口内f的范围寻找dp[i][f] - f * price[i]的最小值。这正是一个经典的滑动窗口最小值问题可以使用单调队列Monotonic Queue在O(1)均摊时间内解决。具体来说当我们计算dp[i1][*]时对于每一个new_f其对应的f窗口是[low, high]其中low max(0, new_f need - C),high new_f need。我们需要维护一个关于f递增且dp[i][f] - f * price[i]也递增实际上是维护最小值所以队列是单调递增的的队列。这样队首元素就是当前窗口的最小值。通过这个优化我们将内层关于b的O(C)循环优化为了均摊O(1)的单调队列操作。总时间复杂度降至O(n * C)空间复杂度O(C)可以滚动数组优化。这在C达到几千时是可以接受的。注意这个优化是本题的核心难点也是区分“暴力DP”和“优化DP”的关键。理解这个“变形滑动窗口最小值”的思想对于解决许多类似带容量限制的序列决策问题非常有帮助。3. C代码实现与逐行解析理论分析完毕我们来看代码实现。我会先给出完整代码然后分段详细解释。#include iostream #include vector #include deque #include algorithm #include climits using namespace std; const long long INF LLONG_MAX / 2; // 防止加法溢出 long long minCostToTravel(vectorint dist, vectorint price, int capacity) { int n dist.size(); // 检查可行性任意相邻两站距离不能超过容量 for (int i 1; i n; i) { if (dist[i] - dist[i-1] capacity) { return -1; // 无法到达 } } // dp[0] 和 dp[1] 滚动数组表示到达前一个站点和当前站点的最小花费 // dp[f] 表示到达某个站点时剩余油量为 f 的最小花费 vectorlong long prev_dp(capacity 1, INF); vectorlong long curr_dp(capacity 1, INF); // 初始化在起点0剩余油量为0花费为0 prev_dp[0] 0; for (int i 0; i n - 1; i) { // i 表示当前所在的站点我们要计算到达 i1 站点的状态 int need dist[i1] - dist[i]; // 从 i 到 i1 需要的油量 fill(curr_dp.begin(), curr_dp.end(), INF); // 重置当前dp数组 // 单调队列优化维护一个 (f, value) 的队列value prev_dp[f] - f * price[i] // 队列保持 value 的单调递增队首最小 dequepairint, long long mq; // 遍历到达 i1 站点时的可能剩余油量 new_f for (int new_f 0; new_f capacity; new_f) { // 对于给定的 new_f在上一站 i 时油量 f 必须满足 // 1. b new_f need - f 0 - f new_f need // 2. b capacity - f - f new_f need - capacity int f_high new_f need; int f_low max(0, new_f need - capacity); // 将新的候选 f (即 f_high) 加入单调队列 if (f_high capacity) { long long candidate_val prev_dp[f_high] - (long long)f_high * price[i]; // 维护队列单调性从队尾移除所有值大于等于当前候选值的元素 while (!mq.empty() mq.back().second candidate_val) { mq.pop_back(); } mq.push_back({f_high, candidate_val}); } // 移除窗口外的队首元素f f_low while (!mq.empty() mq.front().first f_low) { mq.pop_front(); } // 如果队列不为空队首就是窗口 [f_low, f_high] 内 value 的最小值 if (!mq.empty()) { long long min_val mq.front().second; // 状态转移dp[i1][new_f] min_val (new_f need) * price[i] curr_dp[new_f] min_val (long long)(new_f need) * price[i]; // 防止溢出和无效状态传播 if (curr_dp[new_f] INF) curr_dp[new_f] INF; } // 如果队列为空说明没有合法的 f 能转移到 new_fcurr_dp[new_f] 保持 INF } // 滚动数组将 curr_dp 设为下一轮的 prev_dp swap(prev_dp, curr_dp); } // 最终prev_dp 存储的是到达最后一个站点终点时的状态 // 题目通常要求到达终点时油量恰好为0或允许非负这里取0 long long ans prev_dp[0]; return ans INF ? -1 : ans; } int main() { // 示例输入 vectorint dist {0, 100, 300, 450, 600}; // 站点距离起点的位置 vectorint price {5, 9, 3, 8, 0}; // 站点油价终点价格为0 int capacity 200; // 油箱容量 long long result minCostToTravel(dist, price, capacity); if (result -1) { cout 无法到达终点 endl; } else { cout 最小总花费为: result endl; } return 0; }3.1 输入与可行性检查代码开头定义了距离数组dist和价格数组price以及油箱容量capacity。首先进行可行性检查遍历所有相邻站点如果距离差大于容量C则直接返回-1表示问题无解。这是一个重要的边界条件处理避免算法在不可能的情况下运行。3.2 DP数组与初始化我们使用滚动数组prev_dp和curr_dp来节省空间它们的大小都是capacity 1索引代表剩余油量。prev_dp[f]表示到达当前循环的站点 i时剩余油量为f的最小花费。初始化时我们在起点 (i0)剩余油量为0花费为0所以prev_dp[0] 0其他状态为无穷大 (INF)。这里INF设置为LLONG_MAX/2是为了防止在状态转移做加法时发生溢出。3.3 主循环与单调队列优化主循环for (int i 0; i n - 1; i)遍历每一个“出发站”i目标是计算到达下一站i1的所有状态curr_dp[new_f]。对于每一个目标状态new_f到达i1站时的剩余油量我们需要找到所有能转移到它的上一站状态f。关系是b new_f need - f其中need是两站间距离。购买量b必须满足0 b capacity - f。我们将状态转移方程重写为寻找prev_dp[f] - f * price[i]在某个f窗口内的最小值。这个窗口[f_low, f_high]是随着new_f变化而滑动的。单调队列mq的操作是核心入队当计算new_f时对应的f_high成为一个新的候选f。我们计算其价值value prev_dp[f_high] - f_high * price[i]并将其加入队列。在加入前从队尾弹出所有value大于等于当前候选值的元素以保证队列的单调递增性队首始终是最小值。出队检查队首元素对应的f是否已经小于当前窗口的下界f_low如果是则弹出队首因为它已经不在当前有效的窗口内了。取值经过上述维护如果队列不空队首元素的value就是窗口内的最小值。然后我们用公式curr_dp[new_f] min_val (new_f need) * price[i]完成状态转移。这个循环结束后curr_dp就存储了到达站点i1的所有状态的最小花费。然后通过swap(prev_dp, curr_dp)滚动到下一轮。3.4 结果提取与测试循环结束后prev_dp中存储的是到达最后一个站点终点时的状态。根据问题定义我们通常需要剩余油量为0的最小花费即prev_dp[0]。如果这个值大于等于INF说明无法以任何方式在满足条件下到达终点返回-1。在main函数中我给出了一个简单的测试用例。你可以修改dist,price,capacity来验证算法的正确性。4. 算法正确性分析与复杂度4.1 为什么贪心直接在最便宜站买不行这是一个常见的思维误区。假设路径上有三个站A(价格5)、B(价格3)、C(价格8)容量为100A到B距离40B到C距离60。如果只在最便宜的B站买从A出发时你必须买至少40单位油价格5才能到B。到了B你油箱里可能还有一点剩余但为了走完剩下的60你需要在B买油。然而如果你在A站有先见之明知道B站便宜你可能会在A只买刚好到B的油40单位然后在B站加满100单位总花费是40*5 100*3 500。但最优解呢考虑在A站加满100单位花费100*5500然后直接开到C站因为A到C总距离100刚好用完不需要在B和C买油总花费也是500。这个简单例子中两者持平。但如果容量限制更紧或者价格分布更复杂贪心就会出错。例如容量为50A(5), B(10), C(3)A到B距离30B到C距离30。贪心会在最便宜的C站买但你必须先到C。从A到B需要30油你必须在A买至少30花费150。到B后剩余油量20还需要至少10油才能到C必须在B买10花费100总花费250。最优解是在A加满50花费250直接开到C消耗60但只能带50所以此路不通。让我们重新设计容量60A(5), B(10), C(3)A到B30B到C30。贪心A买30到B150B买30到C300总450。最优A买60300直接到C总300。可见贪心并非最优。因此必须通过动态规划来考虑所有可能性。4.2 单调队列优化正确性证明我们优化后的DP等价于原始的二维DP。单调队列维护了dp[i][f] - f * price[i]在滑动窗口内的最小值。对于每个new_f我们通过窗口[f_low, f_high]限制了合法的上一状态f。队列的单调性保证了我们能在O(1)时间内取得最小值而枚举所有b或f需要O(C)时间。因此优化没有遗漏任何可能的状态转移是正确的。4.3 时间复杂度与空间复杂度时间复杂度外层循环O(n)内层对new_f的循环O(C)每个new_f的操作入队、出队、取值是均摊O(1)的。因此总时间复杂度为O(n * C)。空间复杂度使用了两个一维DP数组prev_dp和curr_dp大小均为O(C)以及一个最大容量为O(C)的单调队列。因此总空间复杂度为O(C)。对于n和C都在几千级别的题目这个算法是高效的。5. 常见问题与调试技巧在实际编写和调试这类DP问题时很容易遇到一些坑。下面是我总结的几个常见问题和解决技巧。5.1 整数溢出问题这是最容易忽略的问题。花费可能是非常大的整数距离、价格、容量都大。dp数组和中间计算必须使用long long64位整数。INF的设置也要小心不能直接用LLONG_MAX因为状态转移中会做加法min_val (new_f need) * price[i]可能导致上溢。通常设置为LLONG_MAX / 2是一个安全的选择。const long long INF LLONG_MAX / 2; ... if (curr_dp[new_f] INF) curr_dp[new_f] INF; // 额外的保护5.2 单调队列的实现细节单调队列的实现需要特别注意存储什么队列里我存储了pairint, long long即f和对应的value。存储f是为了方便判断队首元素是否在窗口内f f_low。何时入队对于当前new_f对应的f_high是新的候选。注意判断f_high capacity才入队因为f不能超过容量。维护单调性我们是维护一个值单调递增的队列。所以当新的候选值candidate_val小于等于队尾的值时要弹出队尾直到队列为空或队尾值小于候选值再入队。这样保证了队首始终是窗口内的最小值。何时出队队首当队首元素对应的f小于当前窗口下界f_low时它已经无效需要弹出。5.3 边界条件与初始化起点状态务必正确初始化prev_dp[0] 0其他为INF。终点处理代码中假设终点是最后一个dist且要求最终剩余油量为0。有些问题可能允许终点剩余油量任意非负值那么答案就是min(prev_dp[0], prev_dp[1], ..., prev_dp[capacity])。需要仔细阅读题目要求。不可达判断除了开始的距离检查DP结束后如果ans仍然是INF也表示不可达。5.4 调试与测试用例设计自己设计几个小规模的测试用例手动计算预期结果是调试的最佳方式。简单案例两个站容量足够大。验证是否在起点买了刚好够的油。容量限制案例三个站容量较小迫使必须在中间站加油。验证决策是否正确。价格波动案例价格高低交错验证算法是否会在低价站“囤货”。不可达案例两站距离超过容量验证是否返回-1。例如// 测试1简单两站 dist {0, 100}, price {5, 0}, capacity200。 预期在起点买100油花费500。算法应返回500。 // 测试2容量限制 dist {0, 50, 100}, price {10, 1, 0}, capacity60。 分析从0到50需50油。最优策略在0站买50油花费500到1站在1站加满到60油花费60然后到2站消耗50油剩10油但终点油量要求为0可能需要调整。如果要求终点油量为0则在1站只需买50油花费50总花费550。可以使用打印DP数组的方式来跟踪状态转移过程对于小容量比如C5的情况非常直观。5.5 算法变种与扩展这个“补给站问题”有很多变种初始油量非零旅行者起点有一定油量init_fuel。只需修改初始化prev_dp[init_fuel] 0。油量消耗非1:1可能每单位距离消耗k单位油。只需将need的计算改为k * (dist[i1] - dist[i])并相应调整容量和状态表示。多个资源维度例如同时考虑油量和食物变成二维DP复杂度会大大增加。目标函数变化不是求最小花费而是求在给定预算下的最远距离或者求最小最大单次购买量等。理解了这个核心模型和单调队列优化技巧你就能应对大多数线性序列上的带容量资源调度问题了。这不仅仅是道算法题其思想在物流路径规划、资源采购策略等实际场景中也有应用。下次遇到类似问题不妨先想想能不能套用这个“状态表示 滑动窗口优化”的框架。