LetCode의 Gas Station - 원형 주유소 주유

제목.
There are N gas stations along a circular route, where the amount of gas at station i is  gas[i] .
You have a car with an unlimited gas tank and it costs  cost[i]  of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note: The solution is guaranteed to be unique.
해법
이 문제는 두 단계로 나뉘어 풀었다. 첫 번째 단계는 한 바퀴 돌 수 있는지, 두 번째 단계는 어느 주유소부터 시작할 수 있는지 찾는 것이다.
한 바퀴 주유할 수 있는지 없는지를 확정하다
먼저 단언을 하자면gas수조원소의 합이cost수조원소의 합보다 크면 반드시 한 바퀴를 돌 수 있다.증명은 간단하다. 이렇게 상상할 수 있다. 주유소의 높이는 0이고 주유소의 기름 높이는 가스이다. 코스트는 두 주유소 사이의 구덩이 깊이를 대표하며 기름의 흐름은 같은 방향이다. 그러면 가스의 합이 코스트의 합보다 크면 최종적으로 동적 균형이 잡힌 후 전체 기름 높이>=0이면 반드시 한 바퀴를 돌 수 있다.안 그러면 안돼.
어느 주유소부터
처음에는 제목의 노트를 보지 못했는데, 여러 주유소에서 시작할 수 있을 것 같았다.note 힌트 문제는 유일한 해답이 있습니다. 링의 최대 연속 서열의 합을 찾을 수 있다면 사실점을 찾을 수 있을 것 같습니다. 그러나 링의 최대 연속 감각을 찾는 것이 링의 최대 연속 서열과 (참조)http://blog.csdn.net/xhu_eternalcc/article/details/24880013) 어려우면 바로 힘껏 찾는다. 만약에 어느 주유소에서 N보(주유소의 개수)를 앞으로 두루 돌아다닐 수 있다면 이 주유소부터 다음과 같은 최적화가 필요하다.
det[i]=gas[i]-cost[i]
sum는 i번째 주유소부터 시작하여 모 주유소를 앞으로 두루 돌아다닐 때의 총 남은 기름량
1) 주유소 시작 det[i]>=0
2) i번째 주유소에서 시작하여 앞으로 step 걸음으로 (i+step)%N 주유소,sum<0에 도착하면 x= i+1~(i+step)%N 주유소가 시작점이 될 수 있는지 탐지할 때 주유소 x에서 (i+step)%N까지의 총 남은 기름량sum를 직접 구할 수 있습니다. 코드 참조.
코드

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int sum=0;
        int *det=new (std::nothrow)int[gas.size()];
        for(std::vector<int>::size_type i=0;i<gas.size();++i){
            det[i]=gas[i]-cost[i];
            sum+=det[i];
        }
        if(sum<0){
            delete [] det;
            return -1;
        }
        int step=0;
        for(std::vector<int>::size_type i=0;i<gas.size();++i){
            if(step>0){//i-1      step       <0
                --step;
                if(det[i]<0){
                    sum-=det[i];
                    continue;
                }else if(sum<0){
                    sum-=det[i];
                    continue;
                }
            }else{
                if(det[i]<0)
                    continue;
                sum=det[i]; 
            }
            while(sum>=0&&step<gas.size()){
                ++step;
                sum+=det[(step+i)%gas.size()];
            }
            if(step==gas.size()){
                delete [] det;
                return i;
            }
            else
                sum-=det[i];
        }
    }
};