s******e
发帖数: 108 | 1 You are planning a cross-country trip
along a straight highway with n + 1 gas stations.
You start at gas station 0,
and the distance to gas station i is di miles (0 = d0 < d1 < . . . < dn).
Your car’s gas tank holds G > 0 gallons,
and your car travels m > 0 miles on each gallon of gas.
You start with an full tank of gas[G gallons] (at gas station 0),
and your destination is gas station n.
You may not run out of gas,
although you may arrive at a gas station with an empty tank.
The price of gas at gas station i is pi dollars per gallon (not necessarily
an integer). You cannot sell gas. Give an algorithm to calculate the cost of
the cheapest possible trip. | c**s
发帖数: 159 | 2 贪心 油“分块” 最后可退回
记录油箱里的油量 pair （price, amount)
起初（0, G）因为开始的油不花钱。
我们保证油箱“总是满的” 即所有amount的总和始终为G 但只有用掉的油才花钱。
每到一个加油站 把油加满 但不计算钱。 即加入新的（price， amount）。 存pair得
的结构实际上是个堆 或者multiset (c++)。因为到下个加油站用油的时候 我们从存的
最便宜的块开始用 并且用多少要算钱了 （如果一块用完 则删掉 否则减少amount,直
到可以走到下一个加油站）
本质就是个堆的插入和删除
：You are planning a cross-country trip
：along a straight highway with n + 1 gas stations. | J*****4
发帖数: 1 | 3 每到一个加油站，计算剩余油可以走多远，这个范围内有没比此加油站更便宜的油，如
果有就不加油，直接向前开
如果没有，则边加油(以加满为终止条件)边计算多走的范围内有没有比此加油站更便宜
的油，如果有则加油到此为止break，向前开。 |
|
