贪心算法的分糖果问题大作业
时间: 2023-08-02 07:24:17 浏览: 72
分糖果问题是一道经典的贪心算法问题,其描述如下:
有一群小朋友和一些糖果,每个小朋友有一个评分值,用一个整数表示。现在你需要给这些小朋友分糖果,规则如下:
1. 每个小朋友至少分到一个糖果。
2. 评分高的小朋友必须比他旁边评分低的小朋友分到更多的糖果。
请问,至少需要准备多少个糖果,才能满足以上规则?
解题思路:
首先,我们可以将每个小朋友的评分值看作一个元素,构成一个数组 ratings。然后,我们可以定义一个叫做 candies 的数组,它的初始值全部为 1,表示每个小朋友都分到了一个糖果。
接下来,我们需要遍历两次数组 ratings。第一次遍历,从左到右,如果 ratings[i] 比 ratings[i-1] 大,则 candies[i] = candies[i-1] + 1,即比左边的小朋友多分配一个糖果。
第二次遍历,从右到左,如果 ratings[i] 比 ratings[i+1] 大,则 candies[i] = max(candies[i], candies[i+1]+1),即比右边的小朋友多分配一个糖果。
最后,将 candies 数组中所有元素相加,即为所求的最少需要准备的糖果数量。
代码实现:
```
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> candies(n, 1);
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i-1]) {
candies[i] = candies[i-1] + 1;
}
}
for (int i = n-2; i >= 0; i--) {
if (ratings[i] > ratings[i+1]) {
candies[i] = max(candies[i], candies[i+1]+1);
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans += candies[i];
}
return ans;
}
```