[ARC152C] Pivot
very very easy。首先认识题目中的操作相当于沿 \(y = s\) 进行翻折，那你注意到一个单调的序列翻折之后仍然是单调的，并且翻折仅仅改变了他们差分数组的符号和最小值。那这样就很好做了，假设当前最小值为 \(u\)，极差为 \(d\)，沿 \(y = u + k\) 翻折后最小值变为了 \(2(u + k) - (u + d) = u + 2 * k - d\)，可见变化量为 \(2 * k - d\)，我们最后的任务是最小化最小值，那么直接来裴蜀定理就行了。根据均摊分析时间复杂度是 \(O(n)\) 的。
const int N = 2e5 + 10;
int n;
int a[N];
int main() {
read(n);
for(int i = 1; i <= n; ++i)
read(a[i]);
if(n == 1) {
printf("%d\n",a[1]);
return 0;
}
int d = a[n] - a[1], g = d;
for(int i = 2; i <= n; ++i)
if(2 * (a[i] - a[1]) < d)
g = __gcd(g, d - 2 * (a[i] - a[1]));
printf("%d\n",a[1] % g + d);
}