题目
分析
根据题目出现的章节,这是一道“贪心”的题目。怎么贪心呢?
我们观察一下吃糖果的顺序:如果我们从左到右一个一个地吃,那么对于每一次吃糖果,右边的盒子更重要——因为吃掉它里面的糖果后,它随后还会在下一次作为当前盒子、再下一次作为左边的盒子出现。所以,它里面的糖果被吃得越多,对后续的影响也就越大,也就可以减少总的吃掉的糖果的数量。
实际操作中,我们可以简化操作,只要看当前盒子(i
)和右边的盒子(i+1
)就可以了:先尽可能吃右边盒子里的,如果能吃到满足条件(\(a[i]+a[i+1]\lt x\)),那是最好;如果吃光右边盒子不能达到要求,那么吃当前盒子的。
这个解法是没有后续性的,因为当前盒子在下一次迭代时,成为“左边”的盒子,而我们的吃法是不考虑左边盒子的(因为这个“左边”的盒子在上一次吃的时候,是“右边”的盒子,已经有过一次吃的过程了)。
总结一下:
- 从左到右遍历每对相邻的盒子
(i, i+1)
。 - 如果它们的糖果和超过
x
,先尽可能从右边盒子(i+1)
中吃糖果。 - 如果右边盒子吃完后仍不满足条件,再从当前盒子
(i)
中吃糖果
答案
思考
很有意思的一道“贪心”入门题目!