题解 | #大胃王牛牛#

大家好，我是开车的阿Q，接下来让我们一起来解决这个大胃王牛牛的问题。

题目考察的知识点

贪心算法

题目解答方法的文字分析

这道题目可以使用贪心算法来解决。我们需要找到一个起始牛棚，使得牛牛能够沿顺序走完环形路线的一个周。我们可以通过遍历所有牛棚来找到解答。

具体步骤如下：

1. 首先，我们需要检查是否存在解答。如果所有牛棚的草料总和小于所有牛棚的消耗总和，那么不存在解答，直接返回-1。
2. 否则，从第一个牛棚开始遍历，同时维护当前剩余草料sumGrass和当前剩余消耗sumCost，初始值均为0。
3. 对于每个牛棚i，我们先将grass[i]加到sumGrass上，再将cost[i]加到sumCost上。
4. 每次遍历到一个新的牛棚i时，我们判断当前的sumGrass是否小于sumCost，如果是，则说明当前起始牛棚不可行，将起始牛棚设为下一个牛棚，并将sumGrass和sumCost重置为0。
5. 最后，如果存在解答，则起始牛棚的下标即为所求。

本题解析所用的编程语言

C++

完整且正确的编程代码

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 sumGrass = 0; // 当前剩余草料
        int sumCost = 0; // 当前剩余消耗
        int startIndex = 0; // 起始牛棚下标
        int totalGrass = 0; // 总草料数
        int totalCost = 0; // 总消耗数

        // 计算总草料数和总消耗数
        for (int i = 0; i < n; ++i) {
            totalGrass += grass[i];
            totalCost += cost[i];
        }

        // 如果总草料数小于总消耗数，则不存在解答，直接返回-1
        if (totalGrass < totalCost) {
            return -1;
        }

        // 遍历每个牛棚，寻找可行解
        for (int i = 0; i < n; ++i) {
            sumGrass += grass[i];
            sumCost += cost[i];

            // 如果当前剩余草料不足以支撑当前消耗，说明起始牛棚不可行，
            // 将起始牛棚设为下一个牛棚，并将当前剩余草料和消耗重置为0
            if (sumGrass < sumCost) {
                startIndex = i + 1;
                sumGrass = 0;
                sumCost = 0;
            }
        }

        // 返回起始牛棚下标（下标从1开始）
        return startIndex + 1;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！