题解 | #大胃王牛牛# 贪心

知识点

贪心

思路

首先，grass的总和必须要比cost大，否则是不存在解的，一定走不完一圈。然后我们考虑从前往后模拟这一个过程，如果遇到累积的前缀和为负数，可以认为对结果没有贡献，可以舍弃，从当前的位置开始往后面走。

时间复杂度为

AC Code（C++）

#include <numeric>
#define all(x) (x).begin(), (x).end()
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grass int整型vector 
     * @param cost int整型vector 
     * @return int整型
     */
    int can_complete_circuit(vector<int>& grass, vector<int>& cost) {
        int n = grass.size();
        int s1 = accumulate(all(grass), 0);
        int s2 = accumulate(all(cost), 0);
        if (s1 < s2) return -1;

        // 模拟跑一遍
        int id = 0;
        int cur = 0;
        for (int i = 0; i < n; i ++) {
            cur += grass[i] - cost[i];
            if (cur < 0) {
                id = i + 1;
                cur = 0;
            }
        }
        return id + 1;
    }
};