首页 > 题解 > luogu3550 [POI2013]TAK-Taxis

luogu3550 [POI2013]TAK-Taxis

记一道不错的贪心。

地址:luogu2550

粘过来有乱码就不粘了。

第一眼的感觉肯定是贪心,因为人在还没过车站的时候离车站越远越不划算,浪费的路程也就越多,所以要尽量先叫行驶路程远的车

但是这样只能得50分。

比如说这组数据:

12 4 5
2 3 4 5 8

如果贪心的话显然是回不去的,为什么呢?

我们观察,当人过了车站之后,只需要一辆能从车站到家的车就够了,你有再多其他的车路程短也没用

所以贪心之前需要给自己留一个路程最小的能从车站回家的车,这个车之前不能用。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×