贪心算法--糖果分配 C语言实现_c语言贪心算法分糖果

一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：

1. 每个孩子不管得分多少，起码分到一个糖果。

2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)

给定一个数组 arr 代表得分数组，请返回最少需要多少糖果。

#include <stdio.h>
#include <stdlib.h>
 
int allocation(int *arr, int n){
 
    int *alloc = (int *)malloc(sizeof(int) * n);
 
    alloc[0] = 1;
    for (int i = 1; i < n; ++i) {
        if(arr[i] > arr[i-1]){
            alloc[i] = alloc[i-1] + 1;
        }else{
            alloc[i] = 1;
        }
    }
 
    for (int i = n-1; i >= 0; --i) {
        if(arr[i] < arr[i-1] && alloc[i] >= alloc[i-1]){
            alloc[i-1] = alloc[i] + 1;
        }
    }
 
    int sum = 0;
 
    for (int i = 0; i < n; ++i) {
        sum += alloc[i];
    }
 
    return sum;
 
}
 
int main(){
 
    int arr[8] = {4,1,6,4,10,9,5,1};
 
    int sum = allocation(arr, 8);
 
    printf("sum = %d\n",sum);
 
    return 0;
}