PAT 解题报告 1033. To Fill or Not to Fill (25)

题目描述:

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

加油站问题

算法分析:

算法是贪心: 分一下几种情况进行判断, 逐步贪心求得最优解.

(1) 车子加满油的情况下也到不了下一站, 那么输出最远行程, 结束, 即一旦发现车子一次性能行驶的最远距离小于两站之间的距离, 就结束了, 因为无论如何车子都到不了下一站了

(2) 情况(1) 不发生, 那么好, 顶多我在现在这station加满油, 我总能前进到至少下一站. 那么我希望总的费用尽量少. 这里分三种情况

(2a)首先在当前油量允许的距离范围内, 找到比当前station邮费便宜的车站, 找到其中比当前station便宜的station里面最便宜的(当然了>_<), 直接开过去, 更新油量等数据. 你想啊, 怎么样都是加油, 那么我肯定要找一个最便宜的station去加油咯

(2b)如果(2a)不可能, 也就是我当前的油量能到达的车站里面没有比我当前车站的邮费便宜的, 那我直接开过去不是更加花钱么? 对吧. 所以我需要在我当前车站里面加点油, 注意是加点油, 并不一定是全部加满, 加多少油呢? 那么我需要看看我加满油能到达的所有车站里面有没有比我但钱车站里面便宜的车站, 找到这样的第一个车站, 加满足够的油(不要多加>_<)到达那个车站就行了. 你想啊, 那个车站比我现在的便宜, 即使我需要多加油, 我也是开到那再去加油划算啊, 对吧 >_<

(2c) 好了, 要是连(2b)都不可能, 那我只能乖乖的在当前车站加满油, 然后开到一个所有能到达的车站里面最便宜的那个, 然后在寻找新的范围内可能的车站加油前进了.

注意点:

贪心结构的理解.

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on August 3, 2013