题解：AT_arc129_d [ARC129D] -1+2-1

· · 题解

[ARC129D] -1+2-1

很厉害的推式子题，要多训式子了。

下面默认下标为 0 时是 n，为 n+1 时是 1。

可以先非常典型的设 x_i 表示 i 操作了多少次（x_i\geq 0），那么答案就是 \sum_{i=1}^{n}x_i。

考察 x 的性质，不难发现有 2\times x_i-x_{i-1}-x_{i+1}+a_i=0。

发现上面的式子有个同构，设 b_i=x_i-x_{i-1}，有 b_{i+1}-b_i=a_i。

接着考察性质，发现本题中 \sum_{i=1}^{n} a_i 如果不等于 0 一定无解，所以我们只要考虑 \sum_{i=1}^{n}a_i=0 的情况。

发现把若干个 a 加起来的结果会产生相消，所以不妨加起来：

b_i-b_1=\sum_{j=1}^{i-1}a_j

再发现 \sum_{i=1}^{n}b_i 是等于 0 的，所以不妨把上面那个式子也加起来：

\sum_{i=1}^{n}b_i-b_1=\sum_{i=1}^{n}\sum_{j=1}^{i-1}a_j=\sum_{i=1}^{n}(n-i)a_i

把 -nb_1 移到右边去就构造出了 \sum_{i=1}^{n}b_i，于是有：

\sum_{i=1}^{n}b_i=nb_1+\sum_{i=1}^{n}(n-i)a_i=0

解个方程有：

b_1=-\frac{\sum_{i=1}^{n}(n-i)a_i}{n}

接着我们就可以递推出 b 数组的所有值了。

接着考虑解决 x，因为 x_i=x_{i-1}+b_i，所以只需要确定 x_1 的最小值即可。

由于我们有 x_i\geq 0 的性质，所以说只要递推一遍，将 b 的前缀和中最小的数的相反数和 0 取 max 即可，具体实现细节可看代码。

总时间复杂度 \operatorname{O}(n)。

code