题解 | #大胃王牛牛#

知识点

模拟，贪心

思路

假设grass和cost的长度为n 首先，我们预处理出grass和cost的差s，若s[0~n-1]<0,那必然无解，否则必然有解。

设sum为区间[ans~~n-1]的和 判断完有解后，我们只需要找到一个下标最小的点，使其一直向右遍历，维护sum=sum+s[i]，若sum<0，则需要更新起点下标了。否则，若存在一个点i,使sum[i~n-1]都大于0，那ans即为i+1(下标为0的地方是第一个)

代码c++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grass int整型vector 
     * @param cost int整型vector 
     * @return int整型
     */
    int can_complete_circuit(vector<int>& grass, vector<int>& cost) {
        // write code here
        int sum=0;
        int s[10005];
        int n=grass.size();
        for(int i=0;i<n;i++)
        {
            s[i]=grass[i]-cost[i];
            sum+=s[i];
        }
        if(sum<0)return -1;
        int ans=0;
        sum=0;
         for(int i=0;i<n;i++)
         {  
            sum+=s[i];
            if(sum<0)
            {
                ans=i+1;
                sum=0;
            }
         }
         return ans+1;

    }
};