分糖果问题进阶问题

[编程题]分糖果问题进阶问题

热度指数：780 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。

3. 任意两个相邻的孩子之间的得分如果一样多，糖果数必须相同

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

输入描述:

第一行一个整数N表示数组大小
接下来一行N个整数表示数组内的元素

输出描述:

输出一个整数表示答案

示例1

输入

3
1 2 2

输出

说明

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

示例2

输入

13
0 1 2 3 3 3 2 2 2 2 2 1 1

输出

说明

最优的分配方案为
1 2 3 4 4 4 2 2 2 2 2 1 1

备注:

算法知识视频讲解

Python

汤普森30

N = int(input())
rating = list(map(int, input().split()))

candy = [1]*N
for i in range(1, N):
    if rating[i] > rating[i-1]:
        candy[i] = candy[i-1] + 1
    elif rating[i] == rating[i-1]:
        candy[i] = candy[i-1]
        
for i in range(N-1, 0, -1):
    if rating[i-1] > rating[i]:
        candy[i-1] = max(candy[i-1], candy[i]+1)
    elif rating[i-1] == rating[i]:
        candy[i-1] = max(candy[i-1], candy[i])
        candy[i] = candy[i-1]
        
print(sum(candy))

发表于 2019-08-24 18:56:05 回复(0)