C语言-贪心算法-分发糖果_c语言贪心算法分糖果

1.问题描述

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

2.示例

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

3.源码

 
#include <stdio.h>  
#include <stdlib.h>  // 引入标准库，用于内存分配和程序终止  
 
// 定义candy函数，接收一个整数数组和其大小  
int candy(int* ratings, int ratingsSize) {
    // 为结果数组分配内存，大小与ratingsSize相同  
    int* candies = (int*)malloc(ratingsSize * sizeof(int));
 
    // 将结果数组的所有元素初始化为1，表示每个孩子开始时都得到1个糖果  
    for (int i = 0; i < ratingsSize; i++) {
        candies[i] = 1;
    }
 
    // 第一遍遍历ratings数组，和右边比
    for (int i = 1; i < ratingsSize; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
 
    // 第二遍遍历ratings数组，和左边比  
    for (int i = ratingsSize - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = candies[i] > candies[i + 1] + 1 ? candies[i] : candies[i + 1] + 1;
        }
    }
 
    // 计算总共需要多少糖果  
    int sum = 0;
    for (int i = 0; i < ratingsSize; i++) {
        sum += candies[i];
    }
 
    // 打印每个孩子得到的糖果数量  
    for (int i = 0; i < ratingsSize; i++) {
        printf("孩子 %d 得到了 %d 个糖果\n", i + 1, candies[i]);
    }
    free(candies);
    return sum;
}
 
int main() { 
    int ratings[] = {95,90,98};
    int num = candy(ratings,3);
    printf("总共需要 %d 个糖果\n", num);
    return 0; 
}

4.运行结果