被降智的一道简单题。
题意
\(n\) 个岛屿，第 \(i\) 座桥连接 \(i\) 和 \(i+1\)（第 \(N\) 座桥连接着 \(1\) 和 \(N\)）。
有一条长度为 \(M\) 的旅游序列 \(X\)，你需要按照顺序依次经过这些点，选择断掉一座桥使得旅游经过的桥最少。
分析
设断掉第 \(i\) 座桥会因为绕行增加旅行长度的值为 \(s_i\)。
从 \(p\) 点到 \(q\) 点的最短距离是 \(\min(\vert p-q \vert , n - \vert p - q \vert )\)，那么分类讨论。
不妨设 \(p<q\)。
设多绕行的距离为 \(d = \left\vert n - 2(q - p) \right\vert\)。
分类讨论三种情况。
当 \(q-p < n-(q-p)\) 时
如果断掉了 \(p \sim q-1\) 之间任意一座桥，总的旅程就会增加 \(d\)，所以 \(\forall i \in [p,q), s_i \gets s_i+d\)。
当 \(q-p > n-(q-p)\) 时
如果断掉了 \(1 \sim p-1\) 或 \(q \sim n\) 之间任意一座桥，总的旅程就会增加 \(d\)，所以 \(\forall i \in [1,p) \cup [q,n], s_i \gets s_i+d\)。
当 \(q-p = n-(q-p)\) 时
无论怎么走路程都是一样的，所以不处理。
然后这就是一个区间修改单点查询的问题，可以使用线段树，但是因为只在最后查询，所以可以使用差分。
线段树修改查询为 \(O(n \log n)\)，差分修改查询为 \(O(n)\)。
代码
赛时的线段树做法
//the code is from chenjh
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN 200002
using namespace std;
typedef long long LL;
int n,m;
int x[MAXN];
LL mn[MAXN<<2],lazy[MAXN<<2];//线段树区间修改维护最小值。
#define lson (rt<<1)
#define rson (rt<<1|1)
using ci=const int;
void pd(ci rt,ci l,ci r){
mn[lson]+=lazy[rt],lazy[lson]+=lazy[rt];
mn[rson]+=lazy[rt],lazy[rson]+=lazy[rt];
lazy[rt]=0;
}
void update(ci rt,ci l,ci r,ci L,ci R,ci val){
if(L<=l && r<=R){mn[rt]+=val,lazy[rt]+=val;return;}
pd(rt,l,r);
int mid=(l+r)>>1;
if(L<=mid) update(lson,l,mid,L,R,val);
if(mid<R) update(rson,mid+1,r,L,R,val);
mn[rt]=min(mn[lson],mn[rson]);
}
LL query(ci rt,ci l,ci r,ci L,ci R){
if(L<=l && r<=R) return mn[rt];
pd(rt,l,r);
int mid=(l+r)>>1;
LL ret=0x3f3f3f3f3f3f3f3fll;
if(L<=mid) ret=min(ret,query(lson,l,mid,L,R));
if(mid<R) ret=min(ret,query(rson,mid+1,r,L,R));
return ret;
}
int main(){
cin>>n>>m;
LL ans=0;
for(int i=1;i<=m;i++) cin>>x[i];
for(int i=2;i<=m;i++) ans+=min(abs(x[i]-x[i-1]),n-abs(x[i]-x[i-1]));//不断桥的最小距离。
for(int i=2;i<=m;i++){
int p=x[i-1],q=x[i];
if(p>q) swap(p,q);
if(((q-p)<<1)<n) update(1,1,n,p,q-1,n-((q-p)<<1));
else if(((q-p)<<1)>n){
if(p>1) update(1,1,n,1,p-1,((q-p)<<1)-n);
update(1,1,n,q,n,((q-p)<<1)-n);
}//线段树修改。
}
LL mn=0x3f3f3f3f3f3f3f3fll;
for(int i=1;i<=n;i++) mn=min(mn,query(1,1,n,i,i));//线段树单点查询。
printf("%lld\n",ans+mn);
return 0;
}
复杂度更优秀的差分做法
//the code is from chenjh
#include<cstdio>
#include<algorithm>
#define MAXN 200002
using namespace std;
typedef long long LL;
int n,m;
int x[MAXN];
LL s[MAXN];
int main(){
scanf("%d%d",&n,&m);
LL ans=0;
for(int i=1;i<=m;i++) scanf("%d",&x[i]);
for(int i=2;i<=m;i++){
int p=x[i-1],q=x[i];
if(p>q) swap(p,q);
ans+=min(q-p,n-q+p);//不断桥的最小距离。
if(((q-p)<<1)<n) s[p]+=n-((q-p)<<1),s[q]-=n-((q-p)<<1);
else if(((q-p)<<1)>n){
s[1]+=((q-p)<<1)-n,s[p]-=((q-p)<<1)-n;
s[q]+=((q-p)<<1)-n;
}//差分修改。
}
LL mn=0x3f3f3f3f3f3f3f3fll;
for(int i=1;i<=n;i++) mn=min(mn,s[i]+=s[i-1]);//差分还原的同时取增加的最小值。
printf("%lld\n",ans+mn);
return 0;
}