Codeforces 713E. Sonya Partymaker
题意
给出(n)个人在环上的位置，环长为(m)，可以给每个人钦点一个方向，每个人每秒钟沿着钦定方向走一步，问全环都被人走过的最小时间。
题解
先二分时间(x)，考虑如何判断当前时间是否合法。
考虑破环为链，最后合并答案。
设(f[i])表示前(i)个人最远能覆盖到哪里,(p[i])表示第(i)个人的位置。
分当前的向左还是向右讨论。
还要考虑一种特殊情况为第(i-1,i)之间的空由(i+1)来向左填，让(i)向右扩展，(f[i])从(f[i-2])转移即可。
为什么不会有(i-1,i)之间的空由(i+2)来向左填的情况？
答：如果(p[i+2] - x < p[i])（即(i+2)能够覆盖到(i-1,i)之间的空），那么有(p[i] + x > p[i+2]),于是(i,i+2)之间的空已经被(i)覆盖，将向左的(i+2)改为(i+1)向左，(i+2)向右一定更优。
考虑合并时(1)向左可能覆盖到(n)，会干扰状态转移，于是选取最长的一段空破环为链，取空的长度为二分上界，于是(1,n)之间不会互相覆盖。注意讨论(1)向左或向右，做两次(dp)即可。
难点总结
(dp)转移并非很难，难点在于观察到只会有(i+1)回头填(i-1,i)之间的空，以及选取最长的区间破环为链，避免干扰转移。
Code
#include<bits/stdc++.h>
#define ll long long
#define N 200015
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define lowbit(i) ((i)&(-i))
#define VI vector<int>
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
using namespace std;
int n,m,a[N],p[N],f[N];
bool check(int x){
f[1] = 0;
// < - 1
rep(i,2,n){
f[i] = f[i-1];
if(f[i-1] >= p[i] - 1) f[i] = max(f[i],p[i] + x);
if(f[i-1] >= p[i] - x - 1) f[i] = max(f[i],p[i]);
if(i > 2 && f[i-2] >= p[i] - x - 1) f[i] = max(f[i],p[i-1] + x);
}
if(f[n] >= m - 1 - x) return 1;
// 1 - >
if(p[1] + x < p[2] - x) return 0;
f[2] = max(p[1] + x,p[2]);
rep(i,3,n){
f[i] = f[i-1];
if(f[i-1] >= p[i] - 1) f[i] = max(f[i],p[i] + x);
if(f[i-1] >= p[i] - x - 1) f[i] = max(f[i],p[i]);
if(i > 2 && f[i-2] >= p[i] - x - 1) f[i] = max(f[i],p[i-1] + x);
}
if(f[n] >= m - 1 - max(x - p[2],0)) return 1;
return 0;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d",&m,&n);
rep(i,1,n) scanf("%d",&a[i]),a[i+n] = a[i] + m;
sort(a+1,a+n+n+1);
if(n == 1){
printf("%d
",m-1);
return 0;
}
int pos = 2;
int l = 0,r;
rep(i,2,n+1) if(a[i] - a[i-1] > a[pos] - a[pos-1]) pos = i;
r = a[pos] - a[pos-1] - 1;
rep(i,1,n) p[i] = a[i+pos-1];
int st = p[1];
rep(i,1,n) p[i] -= st;
int ans = 114514;
while(l <= r){
int mid = (l+r)>>1;
if(check(mid)) ans = mid,r = mid-1;
else l = mid+1;
}
printf("%d
",ans);
return 0;
}