Problem 63: Candy Distribution
Problem Statement: Given an array representing the ratings of children standing in a line, distribute candies so that each child gets at least one candy and children with a higher rating than an immediate neighbor get more candies. Compute the minimum candies required.
Input
The first line contains an integer n. The second line contains n space-separated integers representing the ratings.
Output
Print the minimum number of candies required.
Examples
Input:
3
1 0 2
Output:
5
Solution Explanation
Perform two passes: one from left to right ensuring right neighbor condition and one from right to left. Sum the maximum values obtained from both passes for each index.
Solution in C++
#include
#include
#include
using namespace std;
int main(){
int n;
cin >> n;
vector ratings(n);
for(int i = 0; i < n; i++)
cin >> ratings[i];
vector 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(auto c : candies)
ans += c;
cout << ans << "\n";
return 0;
}