请仔细审题,如果你WA#5,请思考是否忽略了这种情况:
(比较极端但很直观)
加油站1 油费10元
一直到加油站100 油费20元
若比较极端一点,从一号加油站开到第一百号加油站,中途没加过油
而且开到100号加油站时,油箱仍然有油,假设还有nL
若需要加满油才能到终点
那么显然,再加(c−n)L油最优
但若算法有误,那么你的算法很可能是先在一号加油站加油,直到刚好可以到最后一个加油站,然后在最后加油站加满,直到终点
请看看自己是否忘记这种情况
(即前面的加油站未必不可加满,不妨先加满再反悔)
顺便求一下这道题的O(n)解法(听说有O(n)的解法%%%)