NOIP初赛复习 - 算法1

29．95

算法分析

设出发城市为0站，目的城市为n+1站。汽车目前在i站(0≤i≤n)，应加多少油，驶往哪一站可使得整个行程的花费最少。我们不妨采用贪心策略，即下一个目的站的单位油价尽可能低于i站；如果所有可达油站的单位油价都高于i站的话，则下一个目的站的单位油价亦应该尽可能地便宜。为此，我们在由i站直接可达的所有油站j (dj-di≤c*D2，i+1≤j≤n+1) 中，计算两个油站序号：

min1—单位油价低于i站且距离最近(以最小代价到达)的一个油站；

min2—在由i站直接可达的所有油站中，单位油价最便宜（但高于i站）的一个油站；

显然，若min1站存在的话，应成为首选的方向，油箱仅加入驶往min1站所需的油量(

dmin1?di)，以便到达min1站时换上更便宜的汽油；反之，若i站直接可达的所有油站

D2dn?1?di≥c*D2)D2的油价均高于i站，则应选择其中油价最低的min2站作为方向，由于i站的油价比min2站便宜，因此不妨让汽车在i站加满油，或者在直接可达目的城市的情况下(

加入驶往最终目的地所需的油量。问题是，汽车在i站时，油箱可能尚有剩油，设剩余油量rest。因此只要在i站加入C*D2-rest的油量，便可将油箱加满；如果i站直接可达目的城市，则加入

dn?1?di-rest的油量，便可使汽车最终到达目的城市。汽车到达min1站时，D2油箱中的油正好耗尽(rest←0)；否则汽车到达min2站时，油箱内的剩余油量应为rest←rest+

dmin2?di。

D2 我们从0站出发，按照上述方法依次类推，直至到达目的城市n+1为止。设 k—当前站(0≤k≤n+1)；

j—由k站驶往的下一目的站(k

k←0； reset←0； cost←0； {出发时的准备} repeat

j←k； min1←0； min2←0；

while (j

if (min1=0)and(pj

if j=k {即便在k站装满油，也无法到达任一站点，则失败退出}

then begin 输出无解信息；halt；end； {then}

if min1>0 {若由k站出发直接可达一个油价更低的油站}

then begin need←

dmin1?dk； {计算k站加入

D2的油量}

if need<0 then need←0 {若min1站位于k站左方，则不需加油}

cost←cost+pk*need； {累计费用}

rest←0； {汽车抵达min1站时油正好耗尽}

k←min1； {由min1出发，继续延伸旅行路线}

end；{then}

else begin {否则，所有可达油站的油价都高于i站}

{若无法直接到达目的城市，则计算油箱在k站满载时需加入的油量；否则计算汽车直达目的城市需新增的油量}

if c*D2≤dn+1-dk

then need←c*D2-rest else need←

dn?1?dk-rest； D2 cost←cost+need*pk； {累计费用}

rest←rest+need-

dmin2?dk； {计算汽车到达min2站时的

D2剩油量}

k←min2； {由min2站出发，继续延伸旅行路线}

end；{else}

until k=n+1； {直至汽车驶至目的城市为止}

输出总费用cost；

这里需要提醒读者的是，并不是所有具备最优子结构的问题（这些问题的最优解包含其子问题的最优解）都可以采用贪心法。下面，我们来考虑一个经典优化问题的两种变形：