题意
分析
-
分数规划之后可以得到式子：(max-min-r*mid+l*midgeq k*mid) .
-
贪心选择，肯定区间的端点是极小或者极大值。特殊处理区间长度 (leq L) 的情况。
-
有两种情况分别对应 (r) 作为最大和最小值。
- (r) 作为最大值：枚举 (a_r-r*mid),查询 (min{a_l-l*mid})并减去.
- (r) 作为最小值：枚举 (a_l+l*mid),查询 (min{a_r+r*mid})并减去.
-
单调队列优化优化查询，因为如果一个点不是最后答案的话这个值一定比最优解大.
-
总时间复杂度为(O(nlogn))。
代码
#include<bits/stdc++.h>
using namespace std;
#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].last,v=e[i].to)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
#define re(x) memset(x,0,sizeof x)
typedef long long LL;
inline int gi(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
return x*f;
}
template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}
template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}
const int N=5e4 + 7;
const double eps=1e-7;
int T,n,k,L,R,tl,hd;
int q[N],a[N],f[2][N][18];
void rmq_init(){
rep(i,1,n) f[0][i][0]=f[1][i][0]=a[i];
for(int k=1;1<<k<=n;++k)
for(int i=1;1<<k<=n-i+1;++i)
f[0][i][k]=min(f[0][i][k-1],f[0][i+(1<<k-1)][k-1]),
f[1][i][k]=max(f[1][i][k-1],f[1][i+(1<<k-1)][k-1]);
}
int query(int l,int r,int g){
int k=0;
for(;1<<k+1<=r-l+1;k++);
if(!g) return min(f[g][l][k],f[g][r-(1<<k)+1][k]);
return max(f[g][l][k],f[g][r-(1<<k)+1][k]);
}
bool check(double mid){
double ans=-1.0*(1e14);
for(int i=L;i<=n;++i) if(1.0*(query(i-L+1,i,1)-query(i-L+1,i,0))/(L-1+k)>=mid) return 1;
hd=1,tl=0;
rep(i,1,n-L+1){
for(;hd<=tl&&i-q[hd]>R-L;++hd);
for(;hd<=tl&&(a[q[tl]]-q[tl]*mid)>=(a[i]-i*mid);--tl);
q[++tl]=i;
Max(ans,(a[i+L-1]-(i+L-1)*mid)-(a[q[hd]]-q[hd]*mid));
}
hd=1,tl=0;
for(int i=n;i>=L;--i){
for(;hd<=tl&&q[hd]-i>R-L;++hd);
for(;hd<=tl&&(a[q[tl]]+q[tl]*mid)>=(a[i]+i*mid);--tl);
q[++tl]=i;
Max(ans,(a[i-L+1]+(i-L+1)*mid)-(a[q[hd]]+q[hd]*mid));
}
return ans>=k*mid;
}
void work(){
n=gi(),k=gi(),L=gi(),R=gi();
rep(i,1,n) a[i]=gi();a[n+1]=0;
rmq_init();
double l=0,r=1000;
while(r-l>eps){
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.4lf
",l);
}
int main(){
T=gi();
while(T--) work();
return 0;
}