AT_joisc2017_c 手持ち花火
一道神秘贪心题。
首先显然是二分速度 \(v\)。
然后发现题意可以被理解成其他人逐渐向 \(k\) 靠近，所以若跑了区间 \([l,r]\) ，那么跑的距离就是 \(x_r - x_l\) ，所以就要尽量增长跑动的时间，而注意到题意不是一碰到就要点燃，所以可以跟着跑，也就是说时间就是 \(T*(r-l+1)\)。
然后就转换成了一开始在区间 \([k,k]\)，要扩展到 \([1,n]\)，若要扩展（距离差为 \(S\)）就要先消耗 $ \frac{S} {2v} $ 的代价，再加上 \(T\) 的代价。
这个怎么做呢？我们发现最优方案一定是每次选择一段区间使得要消耗的代价 \(need\) 小于已有的代价，且最终可以使得代价不降。我们发现这个 \(need\) 是单调递增的，所以我们尽量选较小的区间进行扩展。
但是这样仍然有可能最后会有一段无法再进行扩展的区间。假设现在扩展到 \([L,R]\)，这个时候就考虑 时光倒流，让区间 \([1,n]\) 尝试缩减到现在扩展的区间 \([L,R]\)，因为这样是从最后还有的时间 $ n \times T - \frac{x_n - x_1} {2v} $，反过来考虑，然后就做完了。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define double long double
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef pair<int,int> pir;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return x*f;
}
const int mod=998244353,inf=1e9,N=1e5+5;
int n,k,fl;
double a[N],b[N],T,x[N];
int m1,m2;
inline int expand(double *a,int len,int x,double& cost,double& need){
cost=need=0;
for(int i=x;i<=len;i++){
need=max(need,a[i]-cost);
cost+=T-a[i];
if(cost>=0) return i;
}
return len+1;
}
inline int expand2(double *a,int len,int x,double& cost,double& need){
cost=need=0;
for(int i=x;i<=len;i++){
need=max(need,T-cost);// a_i - (cost - (T - a_i)) = T - cost
cost+=a[i]-T;
if(cost>=0) return i;
}
return len+1;
}
inline bool chk(int v){
m1=m2=0;
for(int i=k-1;i>=1;i--) a[++m1]=(double)(x[i+1]-x[i])/v/2;
for(int i=k+1;i<=n;i++) b[++m2]=(double)(x[i]-x[i-1])/v/2;
int nowa=1,nowb=1,las=0,va=1,vb=1;
double cost_a,cost_b,need_a,need_b,sum=T;
while(nowa<=m1||nowb<=m2){
if((las==1||!las)&&nowa<=m1) va=expand(a,m1,nowa,cost_a,need_a);
if((las==2||!las)&&nowb<=m2) vb=expand(b,m2,nowb,cost_b,need_b);
int fl_a=(va<=m1&&need_a<=sum),fl_b=(vb<=m2&&need_b<=sum);
if(fl_a&&fl_b){
if(cost_a>=cost_b) sum+=cost_a,va=nowa=va+1,las=1;
else sum+=cost_b,vb=nowb=vb+1,las=2;
}
else if(fl_a) sum+=cost_a,va=nowa=va+1,las=1;
else if(fl_b) sum+=cost_b,vb=nowb=vb+1,las=2;
else if(va<=m1||vb<=m2) return 0;
else break;
}
reverse(a+1,a+m1+1); reverse(b+1,b+m2+1);
las=0,m1=m1-nowa+1,m2=m2-nowb+1;
nowa=1,nowb=1,sum=(double)n*T-(x[n]-x[1])/v/2;
va=vb=1;
while(nowa<=m1||nowb<=m2){
if((las==1||!las)&&nowa<=m1) va=expand2(a,m1,nowa,cost_a,need_a);
if((las==2||!las)&&nowb<=m2) vb=expand2(b,m2,nowb,cost_b,need_b);
int fl_a=(va<=m1&&need_a<=sum),fl_b=(vb<=m2&&need_b<=sum);
if(fl_a&&fl_b){
if(cost_a>=cost_b) sum+=cost_a,va=nowa=va+1,las=1;
else sum+=cost_b,vb=nowb=vb+1,las=2;
}
else if(fl_a) sum+=cost_a,va=nowa=va+1,las=1;
else if(fl_b) sum+=cost_b,vb=nowb=vb+1,las=2;
else return 0;
}
return 1;
}
signed main(){
// freopen("in.in","r",stdin);
// freopen("sparklers.out","w",stdout);
n=read(),k=read(),T=read();
for(int i=1;i<=n;i++) x[i]=read();
if(x[n]==0){puts("0"); return 0;}
// cout<<chk(101)<<'\n';
int l=1,r=inf,res=inf;
while(l<=r){
int mid=(l+r)>>1;
if(chk(mid)) r=mid-1,res=mid;
else l=mid+1;
}
cout<<res<<'\n';
}
/*
5 5 10
0
358
1281
5298
5321
*/