问题

Problem Statement

AtCoder 群岛由 N 座岛屿组成，这些岛屿由 N 座桥梁连接，其编号从 1 到 N ，i（1\leq i\leq N-1）号桥双向连接 i 和 i+1 岛，而 N 号桥双向连接 N 和 1 岛。在各个岛屿之间只能靠桥梁通行。

在这些岛屿上，经常会有从 X_1 岛出发，依次游览 X_2, X_3, \dots, X_M 岛的旅行团，游览过程中经过桥梁的总个数定义为游览的长度。

更确切地说，一次游览是满足以下条件的 a_0, a_1, \dots, a_l 序列，其长度为 l：

• 对于所有 j\ (0\leq j\leq l-1)，岛屿 a_j 和 a_{j+1} 之间都有桥连接；
• 对于 0 = y_1 < y_2 < \dots < y_M = l，保证存在 k\ (1\leq k\leq M)，a_{y_k} = X_k。

由于经济原因，这些岛屿将关闭一座桥，以减少维护费用，试求最短的游览长度。

Constraints

• 3\leq N \leq 2\times 10^5
• 2\leq M \leq 2\times 10^5
• 1\leq X_k\leq N
• X_k\neq X_{k+1}\ (1\leq k\leq M-1)
• 所有输入值均为整数。

Input

输入格式如下：

• $N$ $M$
• $X_1$ $X_2$ $\dots$ $X_M$

Output

输出最短的游览长度。

解法

思路

注意到所有岛屿形成了一条环，说明岛与岛之间的通行方式有2种，即沿序号递增方向（N \rightarrow 1 视为增加）或序号递减方向（1 \rightarrow N 视为减小），因此可以开一个 len 数组去存储不经过第 N 个桥时的通行长度（其可以直接通过大序号减小序号得到），易得其相反方向的通行长度为 n - len[i] 。

显然，正常情况下的最小通行长度为 \sum_{i=1}^{n}{\min(len[i], n-len[i])} 。

题目中指出有一座桥将会被“封闭”，这就意味着经过这座桥的路径将不可通行。由于这座桥可能是某一段最短路线的“必经之桥”，因此这座桥被封闭后，一些“最小值”应该被转化为最大值。我们可以开一个 d 数组存储两个通行长度的差值，当检测到某段路径无法走最短路时，就在原有的最小通行长度的基础上加 d[i] 。

那么，该如何去寻找最优解呢？

一种比较容易想的思路（也是我用的思路）就是记录当封闭第 i 座桥时，通行长度会增加多少，最后取其中的最小值。

根据上述思路，可以再开一个大小为 N 的数组去存储上述信息，然后遍历一遍 X 序列，每遍历一次，就将上文提到的 d[i] 加到最短路线上的所有桥点上。

但是很显然，如果直接这样操作，平均时间复杂度会达到 O(n^2) ，肯定会 TLE。

不过，我们根本没必要对最短路径上的所有桥点都进行一遍添加操作！这里可以运用“差分”的思想，在路径起点上增加 d[i] ，在终点上减去 d[i] ，然后通过前缀和来将差分合并，得到最终的数组。

最后在上述数组中提取最小值，加到原有的最小通行长度上，得到最终答案，时间复杂度为 O(n) 。

实现

#include <bits/stdc++.h>
using namespace std;
long long n, m, x[200010], len[200010], d[200010], pre[200010] = {0}, pnt[200010] = {0};
long long ans = 0, mn = 2e18;

int main() {
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> x[i];
  }
  for (int i = 1; i < m; ++i) {
    len[i] = abs(x[i] - x[i - 1]);
    d[i] = abs(n - 2 * len[i]);
    ans += min(len[i], n - len[i]);
    int l = min(x[i], x[i - 1]), r = max(x[i], x[i - 1]);
    if (len[i] < n - len[i]) {
      pre[l] += d[i];
      pre[r] -= d[i];
    } else if (len[i] > n - len[i]) {
      pre[1] += d[i];
      pre[l] -= d[i];
      pre[r] += d[i];
    }
  }
  for (int i = 1; i <= n; ++i) {
    pnt[i] = pnt[i - 1] + pre[i];
    mn = min(mn, pnt[i]);
  }
  ans += mn;
  cout << ans << endl;
  return 0;
}