警示后人
查看原帖
警示后人
416038
羊羊君的幻想楼主2023/7/21 21:18

请仔细审题,如果你WAWA#5,请思考是否忽略了这种情况:

(比较极端但很直观)

加油站11 油费1010元

一直到加油站100100 油费2020元

若比较极端一点,从一号加油站开到第一百号加油站,中途没加过油

而且开到100号加油站时,油箱仍然有油,假设还有nLnL

若需要加满油才能到终点

那么显然,再加(c−n)L(c-n)L油最优

但若算法有误,那么你的算法很可能是先在一号加油站加油,直到刚好可以到最后一个加油站,然后在最后加油站加满,直到终点

请看看自己是否忘记这种情况

(即前面的加油站未必不可加满,不妨先加满再反悔)

顺便求一下这道题的O(n)O(n)解法(听说有O(n)O(n)的解法%%%)

2023/7/21 21:18
加载中...