题意
给定一个长度为 \(N\) 的环，每次选取环上一段并使其中每个元素值均加 \(1\)。给定一个长度为 \(N\) 的序列 \(A\)，环上元素初始值为 \(0\)，求将环变为序列 \(A\) 的最少操作次数。
（\(1 \le N \le 2 \times 10^5, 1 \le A_i \le 10^9\)）。
题解
结论
设 \(M = \max\left\{A_i\right\}, D = \dfrac{1}{2}\sum\limits_{i = 0}^{N - 1}\left\lvert A_i - A_{i + 1 \bmod N}\right\rvert\)，那么答案为 \(\max(M, D)\)。
证明
考虑将区间加操作视为对序列 \(A\) 执行区间减，直至全部减为 \(0\)。
发现每次操作最多使 \(D, M\) 的值减 \(1\)，由此可以证明必要性。
接下来按 \(D, M\) 的大小关系分类讨论来证明充分性。
- \(D = M\)
可以发现此时若序列中存在 \(0\)，那么序列中一定只存在一个只包含 \(M\) 的极长连续段。
若序列中包含多个只包含 \(M\) 的极长连续段，即序列的最大值不相邻，那么序列中一定不含有 \(0\)。
那么一定存在极小的，包含所有序列最大值的区间，对该区间进行操作，一定可以使 \(M\) 和 \(D\) 的值均减少 \(1\)。重复操作至 \(D = M = 0\) 即可。
- \(M > D\)
因为 \(D \ge \max\left\{A_i\right\} - \min\left\{A_i\right\}\)，所以有 \(\min\left\{A_i\right\} > 0\)，那么我们对整个 \(A\) 序列执行操作，一定有 \(M\) 的值减少 \(1\)，\(D\) 的值不改变。重复操作至 \(D = M\) 即可。
- \(D > M\)
此时我们选取任意一个只包含 \(M\) 的极长连续段即可，可以发现 \(D\) 的值一定减少 \(1\)，\(M\) 的值至多减少 \(1\)，重复操作至 \(D = M\) 即可。
至此可以得到结论，只需要 \(\max(D, M)\) 次操作便一定可以完成要求。
总复杂度 \(\mathcal{O}(N)\)，可以通过本题。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N;
std::cin >> N;
ValueVector A(N);
for (auto &iter: A)
std::cin >> iter;
valueType D = 0;
for (valueType i = 1; i < N; ++i)
D += std::abs(A[i] - A[i - 1]);
D += std::abs(A.front() - A.back());
D /= 2;
valueType const M = *std::max_element(A.begin(), A.end());
std::cout << std::max(D, M) << std::endl;
return 0;
}