algorithm - 糖果 - interviewstreet

Question

爱丽丝是一名幼儿园老师。她想给类的 children 一些糖果。所有的 child 都坐成一排，每个 child 都根据自己平时的表现打分。爱丽丝想给每个 child 至少 1 颗糖果。因为 child 是莫名其妙的嫉妒。爱丽丝必须根据任何相邻的 2 个 child 的评分对象给她糖果，如果一个 child 的评分高于另一个，他/她必须得到比另一个更多的糖果。爱丽丝想省钱，所以她总共只给糖果。

输入

输入的第一行是一个整数N，即爱丽丝所在类(class)的 child 人数。以下 N 行中的每一行都包含一个整数，表示每个 child 的评分。

输出

在输出的唯一一行打印一个整数，描述 Alice 必须给出的最小糖果数。

示例输入

3
1
2
2

示例输出

4

解释

Alice 必须给的糖果数量是 1,2 和 1。

约束:

N 并且每个 child 的评分不大于 10^5。

谁能帮帮我？

Answer 1

您可以分两次完成此操作。从每个人都有一颗糖果开始。

首先循环 i 从 1 到 n-1(从零开始)，如果 rating[i] > rating[i-1] 那么 candies[i] = candies[i-1]+1

然后循环i从n-2到0；如果 rating[i] > rating[i+1] then candies[i] = max(candies[i], candies[i+1]+1)

很容易证明这会为您提供有效的糖果分配，因为第二个循环不能破坏第一个循环确定的任何内容，并且所有可能的评级差异都必须由两个循环之一捕获。这将使用最少数量的糖果并不那么明显，但如果您仔细检查每个作业，您可以证明条件证明了每个步骤(特定个人)所需糖果数量的下限。