public class _134 {
    static class Solution1{
        public int canCompleteCircuit(int[] gas, int[] cost) {
            //爆破
            for(int i = 0;i < gas.length;i++){
                int cur = gas[i];
                for(int j = 1;j <= gas.length;j++){
                    cur = cur - cost[(i+j-1)%gas.length];
                    if(cur < 0) break;
                    cur = cur + gas[(i+j)%gas.length];
                }
                if(cur >= 0) return i;
            }
            return -1;
        }
    }
    static class Solution2{
        public int canCompleteCircuit(int[] gas, int[] cost) {
            //discuss中的思路有
            //1. A---->B失败，从AB之间的任何地方作为起点都会失败
            //2. 总gas < 总 cost无法到达
            //思考一个 问题，在2条件成立的情况下，是不是一定存在start，满足条件？
            int remain = 0;
            for(int i = 0;i < gas.length;i++){
                remain += gas[i]-cost[i];
            }
            if(remain < 0) return -1;
            int cur = 0,start = 0;
            for(int i = 0;i < gas.length;i++){
                cur += gas[i]-cost[i];
                if(cur < 0){
                    start = i + 1;
                    cur = 0;
                }
            }
            return start;
        }
    }
}