分糖果问题 #

1. 分糖果问题的介绍
2. 分糖果问题的算法分析
3. 分糖果问题的代码实现

分糖果问题的介绍 #

老师想给排在一列的N个孩子们分发糖果,再分糖果之前老师会根据每个孩子的表现，预先给他们评分。分发糖果的规则如下:
1):每个孩子至少分配到 1 个糖果。
2):相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么老师至少需要准备多少颗糖果呢？例如输入评分: [1,2,2],则可以分别给这三个孩子分发 1、2、1 颗糖果，至少需要四颗糖果

分糖果问题的算法分析 #

对于这个问题，首先初始化每个人的糖果数都是1(满足条件1的最优解)，我们可以分成两步来考虑，来满足相邻的孩子中，评分高的孩子必须获得更多的糖果。
第一步：先保证每一个小朋友只要右边的小朋友分数比他高，那么右边的小朋友糖果数比他多一个(满足条件2右边条件的最优解)。
第二步：后保证每一个小朋友只要左边的小朋友分数比他高，那么左边的小朋友糖果数比他多一个(满足条件2左边条件的最优解)。
将每一步的最优解叠加作为我们最后的最优解。

分糖果问题的代码实现 #

a=[int(i) for i in input().split()]#输入成绩
res=[1]*len(a)#结果列表
for i in range(len(a)-1):#满足条件2右边条件的最优解
    if a[i+1]>a[i]:
        res[i+1]+=1
for i in range(len(a)-1,0,-1):##满足条件2右边条件的最优解
    if a[i-1]>a[i]:
        res[i-1]+=1
print("每个人分到的糖果:{}".format(res))
print("糖果总数：{}".format(sum(res)))

小结 #

• 根据分糖果问题，理解贪心算法
• 掌握分糖果问题求解的贪心算法，能够对实际问题做出分解

习题 #

1. 如果在上述问题中，再加入一个条件3):相邻的小朋友如果分数相同，则所得糖果数相同,该如何求解？