贪心、差分
差分原序列得到序列 $d$，问题等价于使用最小操作次数将 $d$ 中元素全部置 $0$。操作等价于选择一段全为正数的区间 $[l,r]$ 并令 $d_l=d_l-1,d_{r+1}=d_{r+1}+1$。由于原序列中任意元素非负，对任意大于零的元素 $d_l$ 必定存在小于零的元素 $d_{r+1}$ 能够配对操作直至 $d_l=0$。答案为序列 $d$ 中大于零的元素之和。
最后修改：2024 年 05 月 26 日
© 允许规范转载