思路1 一次遍历法
total_remain表示总加油和总耗油之差,如果这个数小于0,则必然完不成绕圈。
为什么如果k+1->end全部可以正常通行,且total_remain>=0就可以说明车子从k+1站点出发可以开完全程?
因为,起始点将当前路径分为A、B两部分。其中,必然有 (1)A部分剩余油量0。 所以,无论多少个站,都可以抽象为两个站点(A、B)。(1)从B站加满油出发,(2)开往A站,车加油,(3)再开回B站的过程。
B剩余的油>=A缺少的总油(因为total_remain>=0)。必然可以推出,B剩余的油>=A站点的每个子站点缺少的油。
Last updated