题解 | #分糖果问题#
分糖果问题
http://www.nowcoder.com/practice/76039109dd0b47e994c08d8319faa352
- 当前孩子的评分比左边的高,也就是递增的,那么当前孩子的糖果数量要比左边个多1。
- 当前孩子的评分等于左边孩子的评分,我们让他降为1,也就是说当前孩子的糖果是1,最 终是不是1,后面还需要在判断。
- 当前孩子的评分低于左边孩子的评分,也就是递减的,这个我们就没法确定当前孩子的糖 果了,但我们可以统计递减孩子的数量(我们可以反向思考,这个递减的序列中,最后一 个肯定是1,并且从后往前都逐渐增加的)
比如数组是[1,3,4,6,8,5,3,1],8是得分的最高点,8 前面的从1开始都是递增的,8后面的从5开始是递减的。也就是说8前面的从1到6,每个 孩 子 的 糖 果 数 量 分 别 是 [1,2,3,4], 那 么 8 后 面 的 从 5 到 1 每 个 孩 子 的 糖 果 数 量 分 别 是 [3,2,1]。那么8的糖果数量就是左右两边的最大值加1,也就是4+1=5。 所以8左边糖果的数量是(1+4) *4/2=10,右边的糖果数量是(1+3) *3/2=6,所以总的 糖果数量是10+6+5=21。