狗家昂赛

wqddmh 发表于 2017-11-27 08:40
可以维护一个向后600公里的最低价格站点序列，每次到一个新位置，直接取最小值就好。那么复杂度降为nlogn

应该是每次找600 km以内第一个比当前价格低的station? 而不是找600范围内最低？
我不太确定，怎么去一个最低价格序列然后可以把时间降低到 nlgn, 求大神指点

dawskiper 发表于 2017-11-30 10:07
好厉害,想了一会儿没有想到反例.
大概的正确性可以这么说明:
假设最优路线不是停在我们指定的这个最低 ...

反例：
price = [4，3，2，1], pos=[0,50,100, 150], 每个加油站之间距离相等50mile，邮箱大小能开600mile，最优解应该是每个加油站都只加够开50mile的油

chouclee 发表于 2018-2-19 18:48
反例：
price = [4，3，2，1], pos=[0,50,100, 150], 每个加油站之间距离相等50mile，邮箱大小能开600mi ...

哦对...我第二点的假设不成立.可能油不够走到最低点,需要立马加.
这样的话还是得O(n^2)的dp了.

lyxuan1208 发表于 2018-2-19 14:20
应该是每次找600 km以内第一个比当前价格低的station? 而不是找600范围内最低？
我不太确定，怎么去一个 ...

嗯，嗯，说得有道理。
要找可行驶范围内的第一个比当前价格低的station和最低的那个station。
逻辑应该是
if exist 第一个比当前价格低的station A
  加油或者不加油，开到A
else
  加油或者不加油，开到最低的那个station
600km内，最低的station可以用维护个堆，每次把新能到达的站点塞进去，如果走了else逻辑，就把顶弹出，同时把所有已经经过的站点都弹出。
第一个比当前价格低的站点，应该也可以用上面这个堆。如果对顶比当前低，那么就顺序遍历，总能找到一个比当前低的站点。如果对顶比当前高，那么就走else逻辑。
所以逻辑重新调整下。
维护一个600km内的站点堆。
if 对顶大于当前站点
  开到对顶
else
找第一个小于当前站点的站点A
  开到A
复杂度，维护堆的操作，最坏情况就是lgn，n次，就是nlgn
if 逻辑就是nlgn
else逻辑因为每个站点在查找过程中只经历了一次，所以是n
综上复杂度是nlgn。

wqddmh 发表于 2018-2-19 22:55
嗯，嗯，说得有道理。
要找可行驶范围内的第一个比当前价格低的station和最低的那个station。
逻辑应该 ...

可以可以
不过我觉得能不能维持一个600km的 deque, deque里维持一个递减序列，deque的last value是最小价格
每次比较last value和当前价格，如果last value低，就加到下一个是station的油, 如果last value高，就意味着当前站点为600km里面最低，加满油

维持一个deque时间复杂度 O（n）总时间O（n）?不知道这个方法有没有错误

lyxuan1208 发表于 2018-2-22 05:05
可以可以
不过我觉得能不能维持一个600km的 deque, deque里维持一个递减序列，deque的last value是最小 ...

感觉上逻辑差不多，就是把堆换成了deque吧？那么问题变成deque的复杂度。
这里用deque似乎不太合适吧？每次往里面插入新值的复杂度就不会是O(1)。所以总复杂度不会是O(n)

wqddmh 发表于 2018-2-22 10:01
感觉上逻辑差不多，就是把堆换成了deque吧？那么问题变成deque的复杂度。
这里用deque似乎不太合适吧？ ...

deque只有offer和poll都是O（1），每个元素进出一次，不是O（n）么

lyxuan1208 发表于 2018-2-22 15:19
deque只有offer和poll都是O（1），每个元素进出一次，不是O（n）么

进的时候要保证顺序就不是O（1）了。

飞机那一题现在利口有了…类似的