题意
给定一个环\(A_1,A_2,\dots,A_n(3\leq n\leq200000，-100\leq A_i\leq100)\)，其中\(A_n\)的后一个数为\(A_1\).
你可以执行任意次如下操作：
选择一个位置\(i(1\leq i \leq n)\)，将\(A_i\)加\(2\)，将与\(A_i\)在环上相邻的两个数减\(1\).
你需要将\(A\)数组中所有元素变为\(0\).求最少操作次数，如果无解输出-1.
- \(3\ \leq\ N\ \leq\ 200000\)
- \(-100\ \leq\ A_i\ \leq\ 100\)
题解
为了方便, 设\(A_0 = A_n, A_{n+1} = A_1\)
显然,如果\(\displaystyle\sum_{i=1}^{N}A_i\neq 0\),一定无解.
考虑设\(a_i\)表示选中\(i\)为中心操作的次数(\(a_i \geq 0\))
则显然有\(2*a_i - a_{i-1} - a_{i+1} = -A_i\), 观察到这个形式有点像差分
所以设\(b_i = a_{i+1} - a_i\), 化为\(a_i + b_i = a_{i+1}\), 又因为是一个环, 所以\(\displaystyle\sum_{i=1}^{N} b_i = 0\)
据此显然可以解出\(b_1, b_2, \dots,b_n\)
因为想让操作数最小, 所以\(a_1\)应该取到保证所有\(a_i \geq 0\)的情况下最小.
答案就是\(\displaystyle\sum_{i=1}^{N} a_i\)
代码
点击查看代码
#include <stdio.h>
#include <iostream>
#include <algorithm>
#define LL long long
const int N = 2e5;
using namespace std;
int n, s[N + 5];
LL ans, b[N + 5], a[N + 5], x[N + 5];
LL max(LL x, LL y) {
return x > y ? x : y;
}
int main() {
// freopen("t.in", "r", stdin);
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%lld", x + i);
s[i] = s[i - 1] + x[i];
}
if (s[n]) {
puts("-1");
return 0;
}
LL sum = 0;
for(int i = 2; i <= n; ++i) sum -= s[i] - x[1];
if (sum % n) {
puts("-1");
return 0;
}
b[1] = sum / n;
for(int i = 2; i <= n; ++i)
b[i] = b[i - 1] + x[i];
LL minx = 0; sum = 0;
for(int i = 1; i < n; ++i) {
sum -= b[i];
if (sum > minx) minx = sum;
}
a[1] = minx;
for(int i = 2; i <= n; ++i) a[i] = a[i - 1] + b[i - 1];
for(int i = 1; i <= n; ++i)
ans += a[i];
printf("%lld\n", ans);
return 0;
}