26971: 分发糖果

greedy, http://cs101.openjudge.cn/practice/26971/

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

输入

第一行包含一个整数n。1 <= n <= 2 * 10^4 第二行包含n个整数，相邻整数间以空格隔开。0 <= ratings[i] <= 2 * 10^4

输出

一个整数

样例输入

Sample1 input:
3
1 0 2
Sample1 output:
5

样例输出

Sample2 input:
3
1 2 2
Sample2 output:
4

提示

tags: greedy

来源: LeetCode 135.分发糖果：https://leetcode.cn/problems/candy/

【邓博文光华管院】思路：贪心和动态规划。初始每个孩子有1个糖果，从左向右遍历，右高于左则更新右糖果数目为左+1。此时满足单向，故还需要反向遍历一次。注意此时应取当前值和前者值+1中的较大者，才能保证两个方向上都满足题意。

python

n = int(input())  
r = list(map(int,input().split()))  
res = [1]*n  
for i in range(1,n):  
    if r[i] > r[i-1]:  
        res[i] = res[i-1]+1  
for j in range(n-1,0,-1):  
    if r[j-1] > r[j]:  
        res[j-1] = max(res[j-1],res[j]+1)  
print(sum(res))

【赵安楠 25 化院】于是耗了2个小时想啊改啊，最后......发现......因为从左往右只能考虑递增，很难考虑递减嘛，那我再从右边考虑一下递增的也就是左边递减的...... 这样的话，一个暂时最高的数，取两次算出来的值里的最大值，一定能同时满足左右两边的要求呀。所以......我先从左往右，如果有递增就12345排，不是递增就1；然后从右往左一样干；最后取两个列表中对应值的最大值，求和。

python

n = int(input())
ratings = list(map(int, input().split()))
left = [1]*n
right = [1]*n

for i in range(n-1):
    if ratings[i] < ratings[i+1]:
        left[i+1] = left[i]+1

ratings.reverse()

for j in range(n-1):
    if ratings[j] < ratings[j+1]:
        right[j+1] = right[j]+1

res = sum([max(left[t], right[n-1-t]) for t in range(n)])
print(res)

python

def candy(ratings):
    n = len(ratings)
    left = [0] * n
    for i in range(n):
        if i > 0 and ratings[i] > ratings[i - 1]:
            left[i] = left[i - 1] + 1
        else:
            left[i] = 1

    right = ret = 0
    for i in range(n - 1, -1, -1):
        if i < n - 1 and ratings[i] > ratings[i + 1]:
            right += 1
        else:
            right = 1
        ret += max(left[i], right)

    return ret

input()
*ratings, = map(int, input().split())
print(candy(ratings))

26971: 分发糖果 ​

26971: 分发糖果