algorithm - HackerRank 糖果分布

Question

问题陈述

爱丽丝想给她类的 children 一些糖果。所有的 child 都坐成一排(他们的位置是固定的)，每个 child 根据他或她在类里面的表现有一个评分。爱丽丝想给每个 child 至少 1 颗糖果。如果两个 child 并排坐着，那么评分高的 child 一定会得到更多的糖果。爱丽丝想省钱，所以她需要尽量减少给 children 的糖果总数。

输出包含 Alice 必须购买的最少糖果数量的一行。

HackerRank problem link

示例输入

3  (no of students )
1  (individual scores)
2  
2

示例输出

4

我的解决方案:

arr = []
for i in range(int(input())):
    arr.append(int(input()))

# candy left to right, candy right to left, and candy array
candy_lr = [1]*(len(arr))
candy_rl = [1]*(len(arr))
candy = []

# traverses from left to right and assigns candy to students
for i in range(1,len(arr)):
    if arr[i]>arr[i-1]:
        candy_lr[i] = candy_lr[i-1]+1

# traverses from right to left and assigns candy to students        
for i in range(len(arr)-2,0,-1):
    if arr[i]>arr[i+1]:
        candy_rl[i] = candy_rl[i+1]+1   

#calculates the total candy needed
for i in range(0,len(arr)):
    candy.append(max(candy_lr[i],candy_rl[i]))
print(sum(candy))

但是，此解决方案仅通过了 11/15 测试用例。这是一个样本 input .对于上述输入，输出应为 33556但我的输出是 33555，在所有 4 个失败的测试用例中，我的输出与预期输出相差 1。我用笔和纸尝试了 15 个元素，效果很好。有没有我遗漏的极端情况？

Answer 1

您的代码有一个索引错误。范围函数不包括最终索引。

for i in range(len(arr)-2,0,-1):

应该是

for i in range(len(arr)-2,-1,-1):

例如:输入

3
2
1
1

当正确答案为 4 时，您的代码输出 3。