送礼物 题解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<deque>
#include<algorithm>

#define maxa 50005
#define me(a) memset(a,0,sizeof(a))

using namespace std;

const double eps=1e-6;
inline void read(int &x){
    x=0;
    char c=getchar();
    while(c<‘0‘||c>‘9‘){
        c=getchar();
    }
    while(c<=‘9‘&&c>=‘0‘){
        x=((x<<1)+(x<<3))+c-‘0‘;
        c=getchar();
    }
    return ;
}
inline int read(){
    int x=0;
    char c=getchar();
    while(c<‘0‘||c>‘9‘){
        c=getchar();
    }
    while(c<=‘9‘&&c>=‘0‘){
        x=((x<<1)+(x<<3))+c-‘0‘;
        c=getchar();
    }
    return x;
}
inline void w1(int x){
    if(x){
        w1(x/10);
        putchar(x%10+48);
    }
    return ;
}
inline void write(int x){
    if(x)w1(x);
    else putchar(‘0‘);
    return ;
}

int n,k,l,r;
int a[maxa];
double ans=0;
deque <int> q1,q2;//min,max
void Find(){
    for(int i=1;i<=n;i++){
        while(!q1.empty()&&q1.front()<=i-l) q1.pop_front();
        while(!q2.empty()&&q2.front()<=i-l) q2.pop_front();
        
        while(!q1.empty()&&a[q1.back()]>=a[i]) q1.pop_back();
        while(!q2.empty()&&a[q2.back()]<=a[i]) q2.pop_back();
        q1.push_back(i);
        q2.push_back(i);
        ans=max(ans,double(max(a[q2.front()]-a[i],a[i]-a[q1.front()]))/double(l+k-1));
    }
    while(!q1.empty())q1.pop_back();
    while(!q2.empty())q2.pop_back();
    return ;
}
//(a[j]-ans*j)-(a[i]-ans*i)>ans*k
double F(double x){
    double ans=0;
    while(!q1.empty())q1.pop_back();
    while(!q2.empty())q2.pop_back();
    for(int i=1;i<=n;i++){
        double y=a[i]-i*x;
        while(!q1.empty()&&q1.front()<=i-r) q1.pop_front();
        while(!q2.empty()&&q2.front()<=i-r) q2.pop_front();
        
        if(!q1.empty()&&i-q1.front()>=l)ans=max(ans,double(y-(a[q1.front()]-q1.front()*x)-x*k));
        
        while(!q1.empty()&&a[q1.back()]-q1.back()*x>=y) q1.pop_back();
        while(!q2.empty()&&a[q2.back()]-q2.back()*x<=y) q2.pop_back();
        
        q1.push_back(i);
        q2.push_back(i);
        
        
    }
    return ans;
    
}


bool check(double x){
    if(F(x)>eps)return true;
    //for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    for(int i=1;i<=(n>>1);i++)swap(a[i],a[n-i+1]);
    //for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    if(F(x)>eps){
        for(int i=1;i<=(n>>1);i++)swap(a[i],a[n-i+1]);
        return true;
    }
    for(int i=1;i<=(n>>1);i++)swap(a[i],a[n-i+1]);
    return false;
}

void clear(){
    ans=0;
    while(!q1.empty())q1.pop_back();
    while(!q2.empty())q2.pop_back();
    return ;
}
int main(){
    for(int T=read();T--;clear()){
        read(n);read(k);read(l);read(r);
        for(int i=1;i<=n;i++)read(a[i]);
        Find();
        double L=ans,R=1005,mid;
        while(L<R-eps){
            mid=(L+R)/2;
            if(check(mid))L=mid;
            else R=mid;
            //cout<<F(mid)<<" "<<L<<":"<<R<<endl;
        }
        printf("%.4lf\n",mid);
    }
    return 0;
    
}