C题-游游的整数操作

C题-游游的整数操作

设 $sum={\sum }_{i=1}^k{x}_{i}sum=\backslash sum\_\{i=1\}^\{k\}x\_i$, $minsumminsum$ 为累加过程中 $sumsum$ 的最小值，若 , 则 $minsumminsum$ 一定出现在 $a_{i}a\_i$ 最后一次变为 $00$ 的位置.

证明 : 假设 $minsumminsum$ 不出现在 $a_{i}a\_i$ 最后一次变为 $00$ 的位置，此时假设它出现在 $a_{i}a\_i$ 某一次但是不是最后一次变为 $00$ 的位置，此时 $a_{i}a\_i$ 为 $00$。下一步若 , $minsumminsum$ 会被更新 ； 故下一步 $x_{i+1}>=1x\_\{i+1\}>=1$，之后累加的过程中，根据假设$a_{i}a\_i$ 再次变成 $00$, 只能说明 ${\sum }_{j=i+1}^n\le 0\backslash sum\_\{j=i+1\}^\{n\}\backslash leq\; 0$ ，但这样 $minsumminsum$ 就又会被更新，所以矛盾。 即 : $minsumminsum$ 一定出现在 $a_{i}a\_i$ 最后一次变为 $00$ 的位置

$kk$ 次操作后, 若 ， $a_i=a_i+sum-(a_i+minsum)=sum-minsuma\_i=a\_i\; +\; sum\; -\; (a\_i\; +\; minsum)=sum-minsum$；

若 $a_i+minsum>=0a\_i+minsum>=0$, $kk$ 次操作后, $a_i=a[i]+suma\_i=a[i]+sum$