n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求,给这些孩子分发糖果: 每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。 用C++实现
时间: 2024-04-28 14:09:47 浏览: 124
C++计算机实现,分数计算,小课程作业。
int candy(int* ratings, int ratingsSize){
int* nums = (int*)malloc(ratingsSize * sizeof(int)); // 存储每个孩子分配的糖果数目
for(int i = 0; i < ratingsSize; i++){
nums[i] = 1; // 每个孩子至少分配一个糖果
}
for(int i = 1; i < ratingsSize; i++){ // 从左到右扫描一遍
if(ratings[i] > ratings[i-1]){
nums[i] = nums[i-1] + 1; // 如果当前孩子评分高于前一个孩子,则分配的糖果数目比前一个孩子多一个
}
}
for(int i = ratingsSize - 2; i >= 0; i--){ // 从右到左扫描一遍
if(ratings[i] > ratings[i+1]){
nums[i] = fmax(nums[i], nums[i+1] + 1); // 如果当前孩子评分高于后一个孩子,则分配的糖果数目比后一个孩子多一个
}
}
int sum = 0;
for(int i = 0; i < ratingsSize; i++){
sum += nums[i]; // 统计总共需要准备的糖果数目
}
free(nums);
return sum;
}
阅读全文