Codeforces 713E. Sonya Partymakert 题解
Codeforces 713E. Sonya Partymakert 题解
阅读目录
Codeforces 713E. Sonya Partymaker
回到顶部
Codeforces 713E. Sonya Partymaker
Link!
题意
给出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\n",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\n",ans); return 0;
}来源：https://www.cnblogs.com/czdzx/p/14810427.html