答案显然满足二分性,先二分一个速度\(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;
}