分发糖果问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了分发糖果问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

代码如下：文章来源地址https://www.toymoban.com/news/detail-685689.html

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n=ratings.size();
        vector<int> nums(n,1);//定义一个数组存放糖果的数量，起始数组中糖果数都为1
        //从左向右遍历
        for(int i=1;i<n;i++)
        {
            if(ratings[i]>ratings[i-1])//如果相邻右边孩子评分大于左边孩子
            {
                nums[i]=nums[i-1]+1;//则右边孩子糖果数等于左边孩子糖果数+1
            }
        }
        
        //第二次遍历，从右向左遍历
        for(int i=n-2;i>=0;i--)
        {
            if(ratings[i]>ratings[i+1]&&nums[i]<=nums[i+1])//如果相邻的左边孩子评分大于右边，并且拥有的糖果数还低于右边
            {
                nums[i]=nums[i+1]+1;//则要在右边孩子糖果数上+1作为左边孩子糖果数
            }
            //如果左边孩子的糖果数本来就大于右边孩子的糖果数，则左边孩子的糖果数不用改变
        }
        int sum=0;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];//计算nums数组里糖果的总数
        }
        return sum;//返回最终糖果数
    }
};

到了这里，关于分发糖果问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！