Codeforces 713E. Sonya Partymaker(二分+环形DP)

Author Avatar
Sakits 5月 15, 2018

题解

  这题官方题解讲的不详细而且时间复杂度不是很靠谱,百度又没有题解,于是我花了一个中午+半节晚修的时间才摸索出一个比较靠谱的做法,难受QAQ…
  首先一眼可以看出是个二分+贪心,然后就掉入了WA的深渊…好像贪心的确是可做的,但是我贪心姿势不够高做不出来
  看题解…里面有一句非常难看懂的句子,根本搞不清语法是怎么样的QAQ各种翻译+挠头,终于大概看懂那句话在讲什么东西…
  最后发现从中能得到的信息就是,二分后DP,(以下内容的0011与官方题解中的相反)设fi,0f_{i,0}为到第ii个人,还没出发,最优情况下位置最小的尚未到达的点与ii位置之差,fi,1f_{i,1}则为已经出发的。
  当fi,00f_{i,0}\leq0时,fi,1=midf_{i,1}=-mid
  当0<fi,0mid0<f_{i,0}\leq mid时,fi,1=0f_{i,1}=0
  好的题解讲了上面两句废话之后说的就跟没说一样了???
enter image description here
  上图前两句话恰是最重要的转移部分,居然省略了…下面三句话讲的方法复杂度我感觉很不靠谱,我觉得是O(n2)O(n^2)的,也可能是我不会证明,希望有大爷能证一下复杂度是对的QAQ…
  难怪这场比赛upvote这么少= =…
  行吧喷完了接着说怎么做QAQ…
  显然最大时间不会超过相邻两点间距离的最大值,所以我们可以找出这两个点,那么从这两个点中的某个点开始DP,这样一定不会有点的路径跨环,题解少了这一步感觉复杂度很不靠谱,至于为啥不靠谱往后看就知道了…
  DP的时候上面题解讲的两句废话是有用的,fi,1f_{i,1}要和下方的转移取min,题解没说,转移部分如下:

fi+1,0=ai+1ai1+fi,1fi+1,1=ai+1aimid,(fi,0>0 && ai+1ai+fi,0)\begin{gathered} f_{i+1,0}=a_{i+1}-a_i-1+f_{i,1}\\ f_{i+1,1}=a_{i+1}-a_i-mid,( f_{i,0}>0\ \&\&\ a_{i+1}-a_i+f_{i,0}) \end{gathered}

  比较重要的是第二句,这也是大多数贪心会GG的地方…
enter image description here
  可能会有两个人这么走,也就是左边那个人需要到的位置如果右边的人也可以到,那么更优的显然是右边的人来走,左边的人往右跑,这样能到达更多的点。
  至于题解为什么不靠谱,就是因为这些边有可能跨环,而题解的做法是跨环就把跑完一次的dp[n][0/1]dp[n][0/1]数组继承给dp[0][0/1]dp[0][0/1]继续跑,直到找到方案或者有些点需要跑的长度超过midmid才能到为止,这样可能会跑很多次DP,实际测试挺少次,但是我并不知道为啥靠谱,我也不想造数据看看能不能卡了。
  而如果按我上方说的找到一个不可能跨环的起点,只需要DP两次就好了,一次是起点向右跑,一次是起点向左跑。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int maxn=500010, inf=1e9;
int n, m;
int f[maxn][2], a[maxn], b[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

inline bool check(int p)
{
	int T=2;
	f[0][0]=f[0][1]=0;
	while(T--)
	{
		int pre0=f[0][0], pre1=f[0][1];
		for(int i=1;i<=n;i++) f[i][0]=f[i][1]=inf;
		for(int i=0;i<n;i++)
		{
			if(f[i][0]<=0) f[i][1]=-p;
			else if(f[i][0]<=p) f[i][1]=min(f[i][1], 0);
			else return 0;
			if(f[i][0]>0)
			{
				int tmp=a[i+1]-a[i]+f[i][0];
				if(tmp<=p) f[i+1][1]=min(f[i+1][1], a[i+1]-a[i]-p);	
			}
			f[i+1][0]=a[i+1]-a[i]-1+f[i][1];
		}
		if(f[n][0]<=pre0 && f[n][1]<=pre1) return 1;
		f[0][0]=f[n][0]; f[0][1]=f[n][1];
	}
	return 0;
}

int main()
{
	read(m); read(n);
	for(int i=0;i<n;i++) read(a[i]);
	int mx=0, mxpos;
	for(int i=1;i<n;i++)
	if(a[i]-a[i-1]>mx) mx=a[i]-a[i-1], mxpos=i-1;
	if(a[0]-a[n-1]+m>mx) mx=a[0]-a[n-1], mxpos=n-1;
	for(int i=mxpos;i<n;i++) b[i-mxpos]=a[i];
	for(int i=0;i<mxpos;i++) b[i+n-mxpos]=a[i]+m;
	memcpy(a, b, sizeof(a)); a[n]=a[0]+m;
	int l=0, r=m;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	printf("%d\n", l);
}