企业官网建设流程全解析

1. 这道题到底在考什么

PAT A1033 这道题，我第一次做的时候直接想歪了。题目大意是：一辆车从起点出发，要开到终点，油箱有最大容量，路上有若干个加油站，每个站油价不同，问怎么加油最省钱，如果到不了终点就输出能跑多远。看起来是个模拟题，实际上它是一道贪心算法的经典题，而且贪心的策略不是一眼能看出来的那种。

我后来跟几个刷题的朋友聊，发现大家在这道题上踩的坑出奇地一致：要么贪心策略想错了，要么边界条件没处理好，要么就是排序之后忘了处理起点没有加油站的情况。这道题在 PAT 甲级里属于那种“思路对了代码不长，思路错了调一下午”的类型。

这篇文章我打算把这道题从头到尾拆一遍。不只是给你一个能 AC 的代码，而是把贪心策略是怎么推导出来的、每一步为什么这么选、边界怎么处理、有哪些容易翻车的地方，全部讲清楚。适合已经会基本 C++ 语法、正在刷 PAT 甲级或者准备算法面试的人看。如果你刚学贪心，这道题也是一个非常好的练手材料。

先说结论：这道题的核心贪心思想是——在能到达的范围内，优先去油价更低的站；如果到不了更低的站，就在当前站加满，然后去能到达的范围里油价最低的那个站。听起来简单，但实现的时候细节很多，下面慢慢展开。

2. 贪心策略的推导过程

2.1 为什么不能用动态规划

我一开始的第一反应是 DP。因为这个问题看起来有“状态”和“决策”：当前在哪个站、油箱里还有多少油、花了多少钱。但仔细一想，油箱容量是浮点数（题目给的是实数），油价也是实数，状态空间是连续的，没法直接做 DP。就算把油量离散化，精度问题也会让你痛不欲生。

那能不能用最短路？把每个加油站当成节点，边权是花费。但问题是花费依赖于你之前加了多少油、油价是多少，不是简单的边权叠加。所以图论建模也很别扭。

排除掉这些之后，剩下的自然就是贪心。贪心的关键在于：你能不能找到一个局部最优的决策，使得它不会影响全局最优。这道题恰好满足这个性质，因为油本身是无差别的——你在 A 站加的油和 B 站加的油，在油箱里混在一起，车烧油的时候不会区分来源。这就意味着，只要你能保证“每一段路程烧的都是当前能用到的最便宜的油”，全局就是最优的。

2.2 核心贪心逻辑的完整推导

我们把问题重新描述一下。车从当前位置出发，油箱里可能有剩余的油，也可以选择加油。目标是到达下一个“决策点”时花费最少。

关键洞察是这样的：如果你当前站的油价是接下来一段路程里最低的，那你应该加满；如果不是，那你只需要加到能跑到那个更便宜的站就行。

为什么？举个例子。假设当前站油价 5 块，下一个站油价 3 块，距离 100 公里，车每公里耗油 1 升，油箱容量 200 升。你在当前站加满 200 升要花 1000 块，但其中 100 升是用来跑这 100 公里的，这 100 升如果留到下一个站加，只要 300 块。所以你只需要在当前站加 100 升（刚好跑到下一个站），然后到下一个站再加满，这样最省。

反过来，如果当前站油价 3 块，下一个站油价 5 块，那你当然应该在当前站加满，因为后面的油更贵。

这就是贪心的核心：永远用当前能接触到的最便宜的油来跑路。

具体来说，对于当前站 i，我们往后面看，在油箱加满能到达的范围内（即距离不超过 maxCapacity * avgDistancePerUnit 的站），找第一个油价低于当前站的站 j：

• 如果找到了 j：在当前站只加到刚好能到 j 的油量，然后开到 j。
• 如果没找到：说明当前站是能到达范围内最便宜的，那就在当前站加满，然后开到能到达范围内油价最低的那个站。

这个策略的直觉是：如果前面有更便宜的，我没必要在这里多买；如果前面都更贵，那我当然在这里尽量多买，然后去一个相对最便宜的站继续。

2.3 起点和终点的特殊处理

有一个很容易忽略的点：起点可能没有加油站。如果起点没有加油站，而终点距离起点大于 0，那车根本没法出发，直接输出 0.00。这个边界我第一次做的时候就忘了，结果有一个测试点一直过不了。

终点的处理也要注意。我们可以把终点也当成一个“加油站”，油价设为 0（或者负无穷），这样贪心的时候自然会优先考虑往终点跑。但要注意，终点不需要加油，所以到达终点时如果油箱还有油，不需要算钱。

另外，如果当前站加满油之后仍然到不了下一个站（或者终点），那就说明无法到达，输出当前能跑的最远距离。

3. 代码实现与关键细节

3.1 数据结构的选择

每个加油站需要存两个信息：距离起点的距离和油价。用一个结构体数组就够了：

struct Station { double price; double distance; };

排序的时候按距离从小到大排。这里有个细节：如果起点有加油站，它的距离是 0；如果起点没有加油站，排序后第一个站的距离大于 0，这时候直接输出 0.00。

我见过有人用map<double, double>来存，其实没必要，数组加排序更直观。

3.2 贪心主循环的写法

主循环的逻辑是这样的：

double tank = 0; // 当前油量 double cost = 0; // 总花费 double maxReach = 0; // 当前能到达的最远距离 int i = 0; // 当前站索引 while (i < n) { // 找能到达范围内第一个比当前站便宜的站 int nextCheaper = -1; for (int j = i + 1; j < n && stations[j].distance <= stations[i].distance + maxCapacity * avgDist; j++) { if (stations[j].price < stations[i].price) { nextCheaper = j; break; } } if (nextCheaper != -1) { // 加到刚好能到 nextCheaper double need = (stations[nextCheaper].distance - stations[i].distance) / avgDist; if (tank < need) { cost += (need - tank) * stations[i].price; tank = need; } tank -= need; i = nextCheaper; } else { // 找能到达范围内油价最低的站 int cheapest = -1; double minPrice = INF; for (int j = i + 1; j < n && stations[j].distance <= stations[i].distance + maxCapacity * avgDist; j++) { if (stations[j].price < minPrice) { minPrice = stations[j].price; cheapest = j; } } if (cheapest == -1) { // 到不了任何站，包括终点 maxReach = stations[i].distance + tank * avgDist; break; } // 加满 cost += (maxCapacity - tank) * stations[i].price; tank = maxCapacity; tank -= (stations[cheapest].distance - stations[i].distance) / avgDist; i = cheapest; } }

这段代码有几个地方需要特别注意。

第一，avgDist是每单位油能跑的距离。题目一般给的是每单位距离耗油量，所以要取倒数。比如题目说每公里耗油 0.5 升，那avgDist = 2，即每升油跑 2 公里。

第二，浮点数比较的时候不要用==，要用一个很小的 epsilon。比如判断tank < need的时候，如果tank和need差在 1e-8 以内，应该认为相等。

第三，循环结束的条件。如果i到达了最后一个站（或者终点），循环结束。但如果中途发现到不了下一个站，要提前 break 并输出能跑的最远距离。

3.3 浮点数精度问题的处理

这道题最恶心的地方就是浮点数。PAT 的测试数据里有一些卡精度的点，如果你直接用double比较大小，可能会因为 0.0000001 的误差导致判断错误。

我的经验是：所有涉及距离和油量的比较，都加一个EPS = 1e-8。比如：

bool lessThan(double a, double b) { return a < b - EPS; } bool equal(double a, double b) { return fabs(a - b) < EPS; }

另外，输出的时候要保留两位小数。如果无法到达终点，输出的是“能跑的最远距离”，这个距离也要保留两位小数。

还有一个坑：如果起点就是终点（距离为 0），那直接输出 0.00，不需要加油。这个情况虽然题目里不一定有，但加上判断更保险。

4. 常见错误与排查方法

4.1 贪心策略写反了

最常见的错误就是把贪心策略搞反了：在当前站能找到更便宜的站时，反而加满了油。这样会导致多花很多冤枉钱。判断方法很简单：如果你在油价高的站加满了油，然后开到油价低的站，那你在高油价站加的那些油就是浪费。

我建议你在纸上画一个简单的例子验证一下。比如三个站：A 油价 5，距离 0；B 油价 3，距离 100；C 油价 4，距离 200。油箱容量 200，每公里耗油 1 升。正确的做法是在 A 加 100 升（花 500），到 B 加满（花 600），到 C 的时候还剩 100 升，够跑到终点。总花费 1100。如果你在 A 加满（花 1000），到 B 的时候还剩 100 升，再加 100 升（花 300），总花费 1300。差了 200 块。

4.2 忘记处理起点没有加油站的情况

这个前面提过了，但值得再强调一次。PAT 的测试数据里有一个点就是起点没有加油站。如果你忘了判断，程序会试图从第一个站开始贪心，但第一个站的距离大于 0，车根本到不了，结果就错了。

正确的做法是：排序之后检查第一个站的距离是否为 0。如果不是，直接输出 0.00 并返回。

4.3 油箱容量和耗油量的单位搞混

题目有时候给的是“每单位距离耗油 X 升”，有时候给的是“每升油跑 X 公里”。这两种表述是倒数关系。如果你搞混了，算出来的距离会差很多。

我的习惯是统一转换成“每升油能跑多少距离”，这样计算maxReach = tank * avgDist的时候比较直观。转换方法就是取倒数：如果每公里耗油 0.5 升，那每升油跑 2 公里。

4.4 循环边界写错导致死循环

贪心主循环里，如果nextCheaper和cheapest都没找到，而且当前站不是最后一个站，那说明到不了任何地方，应该 break。但如果你忘了 break，i不会更新，就会死循环。

还有一种情况：如果cheapest找到了，但它的距离和当前站一样（理论上不会，因为排序后距离严格递增），那i也不会更新。所以排序之后最好去重，或者确保距离严格递增。

4.5 输出格式错误

PAT 对输出格式要求很严格。如果能到达终点，输出总花费，保留两位小数；如果到不了，输出“能跑的最远距离”，也是两位小数。注意是printf("%.2f\n", cost)这种格式，不要多输出空格或者换行。

我见过有人输出的时候用了cout << fixed << setprecision(2) << cost，这个也可以，但要记得加fixed，否则setprecision控制的是有效数字而不是小数位数。

5. 完整代码与测试验证

5.1 完整 AC 代码

把上面的逻辑整合起来，完整的代码如下：

#include <cstdio> #include <algorithm> #include <cmath> using namespace std; const double EPS = 1e-8; const double INF = 1e18; struct Station { double price; double distance; }; bool cmp(const Station &a, const Station &b) { return a.distance < b.distance; } int main() { double maxCapacity, totalDistance, avgDist; int n; scanf("%lf %lf %lf %d", &maxCapacity, &totalDistance, &avgDist, &n); Station stations[510]; for (int i = 0; i < n; i++) { scanf("%lf %lf", &stations[i].price, &stations[i].distance); } // 把终点也加进去，油价设为0，这样贪心会优先往终点跑 stations[n].price = 0; stations[n].distance = totalDistance; n++; sort(stations, stations + n, cmp); // 起点没有加油站 if (stations[0].distance > EPS) { printf("The maximum travel distance = 0.00\n"); return 0; } double tank = 0; double cost = 0; int i = 0; double maxReach = 0; while (i < n) { // 如果当前站就是终点 if (fabs(stations[i].distance - totalDistance) < EPS) { break; } double fullReach = stations[i].distance + maxCapacity * avgDist; int nextCheaper = -1; int cheapest = -1; double minPrice = INF; for (int j = i + 1; j < n && stations[j].distance <= fullReach + EPS; j++) { if (stations[j].price < stations[i].price - EPS) { nextCheaper = j; break; } if (stations[j].price < minPrice - EPS) { minPrice = stations[j].price; cheapest = j; } } if (nextCheaper != -1) { double need = (stations[nextCheaper].distance - stations[i].distance) / avgDist; if (tank < need - EPS) { cost += (need - tank) * stations[i].price; tank = need; } tank -= need; i = nextCheaper; } else if (cheapest != -1) { cost += (maxCapacity - tank) * stations[i].price; tank = maxCapacity; double need = (stations[cheapest].distance - stations[i].distance) / avgDist; tank -= need; i = cheapest; } else { maxReach = stations[i].distance + tank * avgDist; break; } } if (i == n - 1 && fabs(stations[i].distance - totalDistance) < EPS) { printf("%.2f\n", cost); } else { printf("The maximum travel distance = %.2f\n", maxReach); } return 0; }

5.2 测试用例验证

我用几个典型的测试用例来验证一下。

用例一：正常情况

输入：

50 1300 12 8 6.00 1250 7.00 600 7.00 150 7.10 0 7.20 200 7.50 400 7.30 1000 6.85 300

输出应该是749.17。这个用例来自经典教材，可以用来验证基本逻辑。

用例二：起点没有加油站

输入：

50 1300 12 2 7.10 10 7.00 20

输出应该是The maximum travel distance = 0.00。

用例三：到不了终点

输入：

50 1300 12 2 7.10 0 7.00 600

输出应该是The maximum travel distance = 600.00。因为从第一个站加满油能跑 50 * 12 = 600 公里，刚好到第二个站，但第二个站之后没有站了，到不了 1300。

5.3 调试技巧

如果你提交之后有测试点过不了，可以试试这几个方法：

第一，把中间变量打印出来。比如每次循环的时候打印当前站的距离、油价、油箱剩余、总花费，看看哪一步不符合预期。

第二，构造边界用例。比如只有一个站、起点就是终点、油箱容量为 0（虽然题目一般不会给）、油价全部相同等等。

第三，检查浮点数比较。把所有==换成fabs(a - b) < EPS，把所有<换成< a - EPS。

第四，检查数组越界。stations数组的大小要开到n + 1，因为要把终点加进去。如果开到n，加终点的时候就会越界。

6. 从这道题能学到什么

这道题表面上是一道贪心题，实际上它训练的是把实际问题抽象成算法模型的能力。你拿到题目的时候，看到的是“加油”“油价”“油箱容量”这些生活化的概念，但你要能把它抽象成“在约束条件下最小化花费”的优化问题。

另一个收获是边界条件的处理。这道题的边界特别多：起点没有加油站、到不了终点、刚好到达终点、油箱容量为 0、油价相同等等。每一个边界都可能是一个测试点。你在写代码的时候，要养成习惯：先把所有可能的边界列出来，然后逐个处理。

还有一个经验是浮点数比较的套路。在算法竞赛里，浮点数误差是家常便饭。我的习惯是定义一个EPS = 1e-8，所有比较都带上它。虽然有时候会稍微影响性能，但正确性比性能重要得多。

最后说一个我自己的体会：这道题我前前后后做了三遍。第一遍思路错了，第二遍边界没处理好，第三遍才 AC。每次重做的时候，我都会把贪心策略重新推导一遍，确保自己是真的理解了，而不是记住了代码。如果你也在刷这道题，我建议你不要急着看题解，先自己画几个例子，把贪心策略想清楚，然后再动手写。这样收获会大得多。

后续如果你想继续练贪心，可以试试“区间调度”“霍夫曼编码”“最小生成树”这些经典问题。它们的贪心策略各不相同，但核心思想是一样的：找到一个局部最优的决策，并证明它不会影响全局最优。这道题是一个很好的起点。