题解

思路

设在位置 $i$ 执行了 $a_i$ 次操作，则必须满足 $a_i\ge0$ 和 $2a_i-a_{i-1}-a_{i+1}=-A_i$。

做法

令 $b_i=a_{i+1}-a_i$，上式化为 $b_i-b_{i-1}=A_i$。首先必须有 $\sum A_i=0$；在此前提下，先假定 $b_1=0$ 就能由前缀和求出所有 $b_i$ 相对于 $b_1$ 的值。又因为环上 $\sum b_i=0$，可直接求出唯一的 $b_1$；若不是整数，则无解。

得到整数差分 $b_i$ 后，令 $a_1=0$ 并递推出一组相对的 $a_i$。方程的所有解只相差一个全局常数，为了使每个 $a_i\ge0$ 且操作总数最小，应把整个序列上移到最小值恰好为 $0$。此时 $\sum a_i$ 就是答案。

复杂度

整个过程的时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。