|
?
?
Candy Total Accepted: 16494 Total Submissions: 87468My Submissions
?
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?
?
题意：n 个小孩，每个小孩有一个评分。给小孩发糖。要求：
1)每个小孩至少一颗糖
2)评分高的小孩发的糖比他旁边两个小孩的多
思路：左右 dp
用一个数组 candy[n]，表示第 i 个小孩所应该发的最少糖果数
数组 ratings[n] 表示每个小孩的评分
1.从左到右扫描一遍， candy[i] = 1, if ratings[i] <= ratings[i-1] ; candy[i] = candy[i-1] + 1, if ratings[i] > ratings[i-1]
2.从右到左扫描一遍， candy[i] = candy[i], if ratings[i] <= ratings[i+1] ; candy[i] = max(candy[i], candy[i+1] + 1), if ratings[i] > ratings[i+1]
3.accumulate(candy, candy + n, 0)
复杂度： 时间 O(n)， 空间 O(n)
?
int candy(vector
&ratings){
int n = ratings.size();
vector
candy(n, 1); for(int i = 1; i < n; ++i){ candy[i] = ratings[i] <= ratings[i - 1] ? 1 : candy[i - 1] + 1; } for(int i = n - 2; i > -1;--i){ candy[i] = ratings[i] <= ratings[i + 1] ? candy[i] : max(candy[i], candy[i + 1] + 1); } return accumulate(candy.begin(), candy.end(), 0); }
?
|