题目大意
给定一个长度为 \(N\) 的序列 \(A\)，这个序列组成一个环。每次可以选择环上的一段都减去 \(1\)，求最少操作次数使得序列每个位置值均为 \(0\)。
思路
首先考虑一次操作会产生什么影响。
发现，会使得序列的最大值最多减 \(1\)，环的差分序列最多减 \(2\)。
那么我们设 \(M = \max \left\{A_i \right\},D=\dfrac{1}{2}\sum\limits_{1 \leq i \leq N - 1} \left\lvert A_i-A_{i + 1 \bmod{N}} \right\rvert\)。
那么显然答案的下限为 \(\max(M,D)\)，我们需要证明一定能使得答案为 \(\max(M,D)\)。
考虑把情况转化为 \(D=M\) 的情况。
当 \(M > D\) 时
由于 \(D\) 一定大于等于序列的极差，如果存在 \(A_i=0(1 \leq i \leq N)\)，那么一定有 \(D \geq M\)，所以当 \(M \geq D\) 时序列中不存在 \(0\)。
那么此时对整个序列的值都减去 \(1\)，一定会使得 \(M\) 减少 \(1\)，\(D\) 的值一定不变，可以直接重复操作至 \(D=M\)。
当 \(D > M\) 时
可以选择全是最大值的连续区间减去 \(1\)，这样可以使得 \(M\) 至多减 \(1\)，\(D\) 一定减 \(1\)，可以重复操作至 \(D = M\)。
当 \(D=M\) 时
如果只有一个连续最大值段，直接使这段减 \(1\)，可以使得 \(D,M\) 的值均减 \(1\)；
如果有不止一个连续最大值段，此时序列中不存在 \(0\)。因为序列中存在 \(0\) 时一定只存在一个只包含 \(M\) 的连续段。
那么我们可以找到一个最小的包含所有 \(M\) 的区间，对这个区间操作，可以使得 \(D,M\) 的值均减 \(1\)，重复操作至 \(D,M\) 的值均为 \(0\)。
因此，答案一定为 \(\max(M,D)\)。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2000600;
int n,a[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int D = 0,M = 0;
cin >> n;
for(int i = 1;i <= n; i++) {
cin >> a[i];
M = max(M,a[i]);
}
for(int i = 1;i <= n; i++) {
if(i != 1)
D += abs(a[i] - a[i - 1]);
else
D += abs(a[1] - a[n]);
}
D /= 2;
int ans = max(D,M);
cout << ans << endl;
return 0;
}