洛谷:P3817:小A的糖果


洛谷:P3817:小A的糖果

Table of Contents

题目

P3817:小A的糖果

分析

根据题目出现的章节,这是一道“贪心”的题目。怎么贪心呢?

我们观察一下吃糖果的顺序:如果我们从左到右一个一个地吃,那么对于每一次吃糖果,右边的盒子更重要——因为吃掉它里面的糖果后,它随后还会在下一次作为当前盒子、再下一次作为左边的盒子出现。所以,它里面的糖果被吃得越多,对后续的影响也就越大,也就可以减少总的吃掉的糖果的数量。

实际操作中,我们可以简化操作,只要看当前盒子(i)和右边的盒子(i+1)就可以了:先尽可能吃右边盒子里的,如果能吃到满足条件(\(a[i]+a[i+1]\lt x\)),那是最好;如果吃光右边盒子不能达到要求,那么吃当前盒子的。

这个解法是没有后续性的,因为当前盒子在下一次迭代时,成为“左边”的盒子,而我们的吃法是不考虑左边盒子的(因为这个“左边”的盒子在上一次吃的时候,是“右边”的盒子,已经有过一次吃的过程了)。

总结一下:

  1. 从左到右遍历每对相邻的盒子(i, i+1)
  2. 如果它们的糖果和超过x,先尽可能从右边盒子(i+1)中吃糖果。
  3. 如果右边盒子吃完后仍不满足条件,再从当前盒子(i)中吃糖果

答案

Solution

思考

很有意思的一道“贪心”入门题目!

上一篇 下一篇