USACO 2022 Jan Bronze组Drought题解疑问：为何批量降hunger值

问题背景 #

我正在阅读USACO 2022年1月竞赛Bronze组第3题Drought的题解。该题规则为：Farmer John的N头牛排成一行，第i头牛的饥饿值为h_i，仅能选择相邻两头牛i和i+1同时喂食玉米，使二者hunger值各减1。目标是让所有牛的hunger值相同且非负，求最少玉米袋数，否则输出-1。题解中提到从左到右处理牛群的策略：当处理到第i头牛时，若h_i > h_{i+1}，需将i之前所有牛的hunger值降到与h_{i+1}相同，操作方式是选择奇数开头的相邻对（1&2、3&4…i-1&i）同时喂食。我对此存在疑问：为何必须批量降低i之前所有牛的hunger值，而不能仅降低i-1和i的hunger值？

解答 #

核心原因是操作的关联性限制——你每一次操作只能同时降低相邻两头牛的饥饿值，没法单独只调整某一对的差值而不影响前面的牛。

举个简单例子：假设现在前3头牛的饥饿值是[5,5,3]，如果只操作第2和第3对，每次操作后会依次变成[5,4,2]、[5,3,1]、[5,2,0]。这时候第1头牛的饥饿值还是5，和后面的牛差值反而更大，后续还要额外操作去调整前面的牛，完全背离了“最少操作数”的目标，甚至可能导致最终无法让所有牛饥饿值一致。

而按照题解的策略，选择奇数开头的相邻对（比如这里的1&2）操作两次，前两头牛会直接变成[3,3,3]，一步达成前3头饥饿值一致，这才是高效且符合最终目标的操作方式。

往本质上说：我们的目标是让所有牛饥饿值相同，从左到右处理时，前面的牛已经调整到一致状态了。一旦后面出现更小的h_{i+1}，如果只降i和i-1，会打破前面牛群的一致性——i-1前面的牛和i原本是一致的，单独降i和i-1后，前面的牛会比i更高，后续还要花额外操作去修正，反而增加总操作数。

所以批量把前面所有牛降到h_{i+1}的水平，是为了维持前面牛群的一致性，同时一步到位缩小和后面牛的差值，保证每一步处理后，前i+1头牛都朝着“全部一致”的方向推进，最终得到最少的操作次数。

内容的提问来源于stack exchange，提问作者Kopiaobia