ABC338D 题解
KSCD_
·
·
题解
题意
# 思路
暴力求解复杂度必炸，
考虑优化。
显然可以把**计算每条路径**转化成**记录每条路径的贡献**。
------------
## 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 之间这条边后的总路程，
注意到 $l$ 和 $r$ 将 $a$ 数组分成三部分，
第一部分是 $1$ 至 $l-1$ ，贡献为第一种；
第二部分是 $l$ 至 $r-1$ ，贡献为第二种；
第三部分是 $r$ 至 $n$ ，贡献仍为第一种。
特别地，当 $l=1$ 时，第一部分不存在，需要特殊处理。
因此这三部分的区间加操作可以使用差分数组 $s$ 记录。
最后用前缀和恢复 $a$ 数组，输出最小值即可。
具体看代码实现吧。
# 代码
[我的赛时代码](https://atcoder.jp/contests/abc338/submissions/49723789)~~（写得有点啰嗦）~~
以下是我重写的~~对新手友好的~~代码。
```cpp
#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;
}
```