loj 2392「JOISC 2017 Day 1」烟花棒

答案显然满足二分性,先二分一个速度\(v\)

然后显然所有没有点火的都会往中间点火的人方向走,并且如果两个人相遇不会马上点火,要等到火快熄灭的时候才点火,所以这两个人之后应该在一起行动.另外有火的人应该是选前面一个或后面一个没火的人,去和他相遇,所有任意时刻点过火的人都是连续的区间\([L,R](L\le k \le R)\)

现在要做的是推出\([1,n]\)是否可以被全部点火.一个区间\([L,R]\)能被点火,至少要满足的条件为\(x_R-x_L\le 2tv(R-L)\),即这两个人至少要在\(t(R-L)\)时间内相遇.对于一个合法的点火方案,过程中每个区间都满足这个条件,然后考虑证明前驱区间都满足条件的区间一定合法.首先第一个区间\([k,k]\)一定合法;然后在上一个区间合法的情况下,因为两个区间都满足条件,即\(x_R-x_L\le 2tv(R-L)\),那么最右边那个点都能碰到左边那个点,并且如果只有\([L,R]\)之间的点,所有点走不会走出\([x_L,x_R]\),那么其他的点更能碰到新加进来的点了

所以问题变成要把\([k,k]\)拓展成\([1,n]\),每次可以给左右端点移动一格,要使得始终满足\(x_R-x_L\le 2tv(R-L)\),问有没有合法方案.首先把这个柿子化一下,得到\(x_L-2tvL\ge x_R-2tvR\),然后记\(b_i=x_i-2tvi\),那么就是要始终使得\(a_L\ge a_R\).然后每次一直移动左/右端点直到无法移动,为了更优的移动,每次移动左端点时移动到\(L'\),并满足\(b_{L'}\ge b_L\)以及\(\min_{i=L'}^{L} b_i \ge b_R\),这样子移动显然可以给右端点创造出更好的移动条件.右端点的移动也是类似的

如果最后\(L,R\)有一个没移动到最值点,并且不能再移动了,那么就无解.否则,移动到最值点,如果左边右边还有一段路程,那么这时直接移动显然可能会导致无解.现在考虑把左右端点设为\(1\)和\(n\),然后分别移动到\(L\)和\(R\),这个过程可以套用前面的做法.因为这个移动过程可逆,并且倒着移动过程也是和正着移动过程有相同性质,所以是合法的

#include<bits/stdc++.h>

#define LL long long

#define uLL unsigned long long

#define db long double

using namespace std;

const int N=1e5+10;

const db eps=1e-4;

int rd()

{

	int x=0,w=1;char ch=0;

	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

	return x*w;

};

int n,kk,t,ft[N],nt[N];

db a[N],b[N],bb[N],mid,mi[N],mx[N];

int s1[N],t1,s2[N],t2;

bool ck(int n,db kk,bool oo)

{

	t1=t2=0;

	for(int i=1;i<=kk;++i)

	{

		db nw=b[i];

		while(t1&&b[s1[t1]]<b[i]) nw=min(nw,mi[t1]),--t1;

		s1[++t1]=i,mi[t1]=nw;

	}

	for(int i=n;i>=kk;--i)

	{

		db nw=b[i];

		while(t2&&b[s2[t2]]>b[i]) nw=max(nw,mx[t2]),--t2;

		s2[++t2]=i,mx[t2]=nw;

	}

	int ll=kk,rr=kk+oo;

	while(t1>1||t2>1)

	{

		bool fg=0;

		while(t1>1&&mi[t1]>=b[rr]) fg=1,--t1,ll=s1[t1];

		while(t2>1&&b[ll]>=mx[t2]) fg=1,--t2,rr=s2[t2];

		if(!fg) break;

	}

	if(t1>1||t2>1) return 0;

	if(ll==1&&rr==n) return 1;

	if(oo) return 0;

	int tp=0;

	for(int i=ll;i;--i) bb[++tp]=b[i];

	for(int i=n;i>=rr;--i) bb[++tp]=b[i];

	memcpy(b,bb,sizeof(db)*(tp+1));

	return ck(tp,ll,1);

}

int main()

{

	n=rd(),kk=rd(),t=rd();

	for(int i=1;i<=n;++i) a[i]=rd();

	db l=0,r=1e9,ans=1e9;

	while(r-l>eps)

	{

		mid=(l+r)/2;

		for(int i=1;i<=n;++i) b[i]=a[i]-2*mid*t*i;

		if(ck(n,kk,0)) ans=mid,r=mid-eps;

		else l=mid+eps;

	}

	printf("%d\n",(int)ceil(ans-eps*2));

	return 0;

}

巴特西

loj 2392「JOISC 2017 Day 1」烟花棒

最新文章

热门文章