题解

思路

一次操作至多让序列最大值增加 $1$，所以答案至少为 $M=\max A_i$。

做法

同时考察环上相邻元素差的绝对值之和：一次给连续区间加一只会改变区间两端的差，因此该和至多增加 $2$。令 $D=\frac12\sum_{i=0}^{N-1}|A_i-A_{(i+1)\bmod N}|$，答案还至少为 $D$。

这个下界可以达到。把操作倒过来看：若 $M>D$，序列中不可能有零，可将整环减一；若 $M<D$，选择一个只由最大值组成的极大连续段减一；若 $M=D$，最大值只有一个极大段时减去该段，否则序列同样没有零，可减去包含所有最大值的最短环形区间。每一步都能使 $\max(M,D)$ 恰好减少一，直到全零。因此答案是 $\max(M,D)$。

复杂度

只需一次线性扫描，时间复杂度 $O(N)$，空间复杂度 $O(N)$。