本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-29 07:15:30

题意

$n$ 个点顺序连接的环，边长为 $1$，去掉其中一条边，使顺序访问 $m$ 个点的路程最短，求最短路程。

思路

暴力求解复杂度必炸， 考虑优化。

显然可以把计算每条路径转化成记录每条路径的贡献。

1.路径计算

若求两点 $l,r$ 间距离，可以先令 $r \gt l$，方便处理。

我们发现在环上从 $r$ 走到 $l$ 只有两种路径，

且断掉一条边以后为一条链，即只有唯一的路径，

那么我们就可以先求出两种路径分别的长度：

• 其中直接从 $1$ - $n$ 内部走（即 $l,l+1 \cdots r-1,r$）的路程即 $(r-l)$

• 而另一种为经过 $n$ 和 $1$ 连接的这条边（即 $r,r+1 \cdots 1,2 \cdots l-1,l$）

通过分析可知两种的路径长度和为环的总长度 $n$

则第二种的路径长为 $(n-(r-l))$

2.记录求解

因为最终要求的是 $(m-1)$ 段路程的和最小，

考虑把每一段路程分别计算，最后再一起求和。

设 $a_i$ 表示断掉连接 $i$ 和 $i+1$ 之间这条边后的总路程，

$a_n$ 即为断开 $n$ 和 $n-1$ 之间边时的总路程，

注意到 $l$ 和 $r$ 将 $a$ 数组分成三部分，

第一部分是 $1$ 至 $l-1$ ，贡献为第一种；

第二部分是 $l$ 至 $r-1$ ，贡献为第二种；

第三部分是 $r$ 至 $n$ ，贡献仍为第一种。

特别地，当 $l=1$ 时，第一部分不存在，需要特殊处理。

因此这三部分的区间加操作可以使用差分数组 $s$ 记录。

最后用前缀和恢复 $a$ 数组，输出最小值即可。

具体看代码实现吧。

代码

我的赛时代码（写得有点啰嗦）

以下是我重写的对新手友好的代码。

#include<iostream>
using namespace std;
const int N=2e5+10;
int n,m,x[N];
long long ans=1e18,s[N];\/\/初始化，记得开longlong 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>x[i];
	for(int i=1;i<m;i++)\/\/处理(m-1)段距离的贡献
	{
		int l=x[i];
		int r=x[i+1];
		if(l>r) 
			swap(l,r);\/\/使r>l 
		int sn=r-l;\/\/第一种的距离
		int sw=n-sn;\/\/第二种的距离
		if(l==1)
			s[l]+=sw;\/\/s[l]即s[1]，断掉1和2之间的边时只能先到n，即第二种
		else
		{
			s[1]+=sn;
			s[l]+=(sw-sn);
		}
		s[r]+=(sn-sw);
	}
	for(int i=1;i<=n;i++)
	{
		s[i]+=s[i-1];
		ans=min(ans,s[i]);
	}\/\/求前缀和及最小值答案 
	cout<<ans;
	return 0;
}