Luogu P1016 [NOIP 1999 提高组] 旅行家的预算
<p>这是一道经典的贪心算法问题。它考验的不仅仅是找到一个看似正确的贪心策略，更是对策略背后逻辑的严谨思考，以及对问题状态的完整建模。很多同学（包括你最初的代码）都会掉入同一个陷阱，这篇题解将带你绕开它。</p><h2 id="问题描述">问题描述</h2>
<p>一辆汽车需要从起点行驶到终点，途中有若干加油站。给定汽车油箱容量、每升油能行驶的距离、以及每个加油站的油价和位置。目标是计算从起点到终点所需的最小花费。如果无法到达，则输出 "No Solution"。</p>
<h2 id="核心思想贪心策略的正确打开方式">核心思想：贪心策略的正确打开方式</h2>
<p>贪心算法的精髓在于每一步都做出<strong>当前看起来最优</strong>的选择。那么，在这个问题里，当车停在某个加油站 <code>i</code> 时，“最优选择”到底是什么？</p>
<p>这需要分两种情况讨论：</p>
<h3 id="情况一在满油可达范围内有比当前油站-i-更便宜的油站">情况一：在满油可达范围内，有比当前油站 <code>i</code> 更便宜的油站</h3>
<ul>
<li><strong>决策</strong>：既然前方有更便宜的油，我们显然不应该在当前这个较贵的站点加太多油。加多少最合适？<strong>刚好能开到那个最近的、比当前便宜的油站 <code>j</code> 即可</strong>。</li>
<li><strong>理由</strong>：我们的目标是尽快用上更便宜的油。任何在当前站多加的、超出到达 <code>j</code> 站所需的油，都是在用“更贵的成本”行驶本可以由“更便宜成本”覆盖的距离，这显然不划算。</li>
</ul>
<h3 id="情况二在满油可达范围内所有油站都比当前油站-i-贵或一样贵">情况二：在满油可达范围内，所有油站都比当前油站 <code>i</code> 贵（或一样贵）</h3>
<ul>
<li><strong>决策</strong>：这说明当前站 <code>i</code> 的油是接下来一段路程中最划算的了。我们应该充分利用这个优势。所以，应该在当前站<strong>把油箱加满</strong>，然后径直开往这个可达范围内<strong>油价最低的那个油站 <code>k</code></strong>。</li>
<li><strong>理由</strong>：通过加满油，我们用当前相对便宜的油，行驶了最远的距离，最大限度地减少了未来在更贵的油站加油的需求。选择去 <code>k</code> 站，是为了让下一次决策时，我们的起点油价尽可能低。</li>
</ul>
<h2 id="警示录常见的错误陷阱">警示录：常见的错误陷阱</h2>
<h3 id="陷阱一忽略剩余油量导致错误的成本计算这是你代码的根本问题">陷阱一：忽略“剩余油量”，导致错误的成本计算（这是你代码的根本问题）</h3>
<p>我最初的代码逻辑是：从站 <code>i</code> 找到目标站 <code>j</code>，然后计算 <code>(a.dis - a.dis) * a.co / per</code> 作为花费。这个公式隐含了一个致命的假设：<strong>每次出发时油箱都是空的</strong>。</p>
<p><strong>【致命场景】</strong></p>
<ul>
<li>A站（<code>dist=0, price=5.0</code>），B站（<code>dist=400, price=10.0</code>），终点C（<code>dist=600</code>）。</li>
<li>油箱50升，每升跑10公里。满油跑500公里。</li>
</ul>
<ol>
<li>
<p><strong>错误逻辑</strong>：</p>
<ul>
<li>在A站，只能去B站。花费 <code>(400/10) * 5.0 = 200</code> 元。</li>
<li>到达B站后（假设油箱空了），要去C站。花费 <code>(200/10) * 10.0 = 200</code> 元。</li>
<li>总花费：<strong>400元</strong>。</li>
</ul>
</li>
<li>
<p><strong>正确逻辑</strong>：</p>
<ul>
<li>在A站，发现前方B站更贵。<strong>决策：加满油</strong>。花费 <code>50 * 5.0 = 250</code> 元。油箱现有50升。</li>
<li>开车去B站，消耗40升油。<strong>到达B站时，油箱还剩10升！</strong></li>
<li>在B站，到终点C需要20升油。因为油箱里有10升，所以<strong>只需要再买10升昂贵的油</strong>。花费 <code>10 * 10.0 = 100</code> 元。</li>
<li>总花费：250元（A站加油） + 100元（B站加油） = <strong>350元</strong>。</li>
</ul>
</li>
</ol>
<p><strong>结论：</strong> 如果不追踪 <code>current_oil</code>（当前油量）这个状态，你的算法永远无法做出“用之前剩下的便宜油”这种决策，从而导致计算结果偏高。</p>
<h3 id="陷阱二错误的贪心目标">陷阱二：错误的贪心目标</h3>
<p>我最初代码的另一个问题是，在所有可达站里，总是选择那个油价最低的。这在某些情况下不是最优的。正确的做法是区分上述两种情况，做出不同的决策。</p>
<h2 id="建模与实现">建模与实现</h2>
<p>为了优雅地实现正确的贪心策略，我们可以做一些巧妙的建模：</p>
<ol>
<li><strong>统一站点</strong>：将<strong>起点</strong>和<strong>终点</strong>都视为特殊的“加油站”。
<ul>
<li>起点的距离为0，油价为初始油价。</li>
<li>终点的距离为总距离，油价设为0（这能确保它总会被优先考虑，逻辑统一）。</li>
</ul>
</li>
<li><strong>排序</strong>：将所有站点（包括起点和终点）放入一个列表，并按距离从小到大排序。</li>
<li><strong>追踪状态</strong>：在循环中，必须维护 <code>current_oil</code> 和 <code>total_cost</code> 两个核心变量。</li>
</ol>
<h2 id="参考代码实现">参考代码实现</h2>
<pre><code class="language-python">import sys
class Oil:
def __init__(self, co=0, dis=0):
self.co = co
self.dis = dis
input = lambda: sys.stdin.readline().strip()
dis, c, per, start_co, n = map(float, input().split())
n, maxn, a = int(n), c * per,
for i in range(n):
x, y = map(float, input().split())
a.append(Oil(y, x))
a.append(Oil(co=0, dis=dis))
a.sort(key=lambda item: item.dis)
n = len(a) - 1
if a.dis or a.dis - a.dis > maxn:
print("No Solution")
exit()
i, total_cost, current_oil = 0 , 0.0, 0.0
while i < n:
has_cheaper_station = False
for j in range(i + 1, n + 1):
if a.dis - a.dis > maxn:
break
if a.co < a.co:
dist_to_j = a.dis - a.dis
oil_needed = dist_to_j / per
if current_oil < oil_needed:
oil_to_buy = oil_needed - current_oil
total_cost += oil_to_buy * a.co
current_oil += oil_to_buy
current_oil -= oil_needed
i, has_cheaper_station = j, True
break
if has_cheaper_station: continue
cheapest_next_idx = -1
min_price_in_range = float('inf')
for j in range(i + 1, n + 1):
if a.dis - a.dis > maxn:
break
if a.co < min_price_in_range:
min_price_in_range, cheapest_next_idx = a.co, j
if cheapest_next_idx == -1:
print("No Solution")
exit()
oil_to_buy = c - current_oil
total_cost += oil_to_buy * a.co
current_oil, dist_to_target = c, a.dis - a.dis
oil_needed, i = dist_to_target / per, cheapest_next_idx
current_oil -= oil_needed
print("%.2f" % total_cost)
</code></pre>
<h2 id="总结与反思">总结与反思</h2>
<p>解决算法问题，尤其是贪心问题时：</p>
<ol>
<li><strong>策略要严谨</strong>：不能只凭直觉。需要仔细分析不同情况，并证明每种情况下的局部最优选择。</li>
<li><strong>状态要完整</strong>：问问自己，“我的程序需要记住什么信息才能做出下一步决策？”。在这个问题里，<code>current_oil</code> 就是被遗忘的关键记忆。</li>
<li><strong>建模要巧妙</strong>：好的数据建模（如将起点终点视为普通站点）可以大大简化逻辑，避免复杂的边界条件判断。</li>
</ol><br><br>
来源：https://www.cnblogs.com/AFewMoon/p/18999362
頁:
[1]