本文共 1613 字，大约阅读时间需要 5 分钟。

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Example 1:

Input: [1,0,2]Output: 5Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]Output: 4Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.             The third child gets 1 candy because it satisfies the above two conditions.

题意：老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。按照以下要求，帮助老师给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

解法 贪心

感觉和PAT（乙级）2020年秋季考试中的胖达与盆盆奶差不多，代码也很简单。关键在于，一定要在确定一边之后，再确定另一边——例如先让每一个孩子和左边比较，然后再和右边比较；如果两边一起考虑就会顾此失彼。

class Solution {
   public:    int candy(vector
   
    & ratings) {
           if (ratings.size() <= 1) return ratings.size();        int n = ratings.size(), ans = 0;        vector
    
      candies(n, 1);        for (int i = 1; i < n; ++i)             if (ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) candies[i] = candies[i - 1] + 1; //当前的值大于左部的        for (int i = n - 2; i >= 0; --i)            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) candies[i] = candies[i + 1] + 1; //当前的值大于右部的        for (int i = 0; i < n; ++i) ans += candies[i];        return ans;    }};
    
   

运行效率如下：

执行用时：44 ms, 在所有 C++ 提交中击败了59.76% 的用户内存消耗：16.9 MB, 在所有 C++ 提交中击败了65.11% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/111602874 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！