派分糖果

[编程题]派分糖果

热度指数：2586 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有N个孩子站成一排，每个孩子有一个分值。给这些孩子派发糖果，需要满足如下需求：

1、每个孩子至少分到一个糖果

2、分值更高的孩子比他相邻位的孩子获得更多的糖果

求至少需要分发多少糖果？

输入描述:

0,1,0

输出描述:

示例1

输入

5,4,1,1

输出

算法知识视频讲解

Python

汤普森30

nums = list(map(int, input().split(',')))
candy = [1 for _ in range(len(nums))]
for i in range(1, len(nums)):
    if nums[i] >nums[i-1]:
        candy[i] = candy[i-1] +1
for i in range(len(nums)-2, -1, -1):
    if nums[i] > nums[i+1]:
        candy[i] = max(candy[i], candy[i+1]+1)
print(sum(candy))

发表于 2019-09-01 15:29:26 回复(0)

Python

ElonB

""""
从左至右，看自己左侧的分数，若比自己小，在他的基础上加一
从右至左，看自己右侧的分数，若比自己小，max(自己，右侧+1)
"""

if __name__ == "__main__":
    a = list(map(int, input().strip().split(',')))
    n = len(a)
    ans = [1] * n
    for i in range(1, n):
        if a[i] > a[i - 1]:
            ans[i] = ans[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if a[i] > a[i + 1]:
            ans[i] = max(ans[i], ans[i + 1] + 1)
    print(sum(ans))

发表于 2019-07-16 12:23:27 回复(1)