首页 > 试题广场 >

分糖果问题

[编程题]分糖果问题
  • 热度指数:66859 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
一群孩子做游戏,现在请你根据游戏得分来发糖果,要求如下:

1. 每个孩子不管得分多少,起码分到一个糖果。
2. 任意两个相邻的孩子之间,得分较多的孩子必须拿多一些糖果。(若相同则无此限制)

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

要求: 时间复杂度为 空间复杂度为

数据范围:  ,

示例1

输入

[1,1,2]

输出

4

说明

最优分配方案为1,1,2 
示例2

输入

[1,1,1]

输出

3

说明

最优分配方案是1,1,1 
int candy(int* arr, int arrLen ) {    
    int i = 0;
    int sum = 0;
    int temp[arrLen];

    for(i = 0; i < arrLen; i++)
    {
        temp[i] = 1;
    }   
    for(i = 1; i < arrLen; i++)
    {
        if(arr[i] > arr[i-1])
        {
            temp[i] = temp[i-1] +1;
        }
    }
    for(i = arrLen - 1; i > 0; i--)
    {
        if(arr[i-1] > arr[i])
        {
            if(temp[i-1] <= temp[i])
            {
                temp[i-1] = temp[i] + 1;
            }
        }
    }
    for(i = 0; i < arrLen; i++)
    {
        sum += temp[i];
    }
    
    return sum;
}
发表于 2022-03-11 15:16:30 回复(0)