[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);
}