考虑二分答案
对于一个区间一定是一边最大一边最小是最优的，还有不够补足L的情况，这个RMQ就好
枚举右端点是最大/最小，单调队列搞搞就完了
#include#include #include #include #include #include using namespace std;const int _=1e2;const int maxn=5e4+_;const int mbit=30;int n,K,L,R,a[maxn];namespace ST{ int Bin[mbit],Log[maxn],mx[mbit][maxn],mn[mbit][maxn]; void main() { Bin[0]=1;for(int i=1;i<=25;i++)Bin[i]=Bin[i-1]*2; Log[1]=0;for(int i=2;i<=n ;i++)Log[i]=Log[i/2]+1; for(int i=1;i<=n;i++)mx[0][i]=mn[0][i]=a[i]; for(int j=1;Bin[j]<=n;j++) for(int i=1;i+Bin[j]-1<=n;i++) mx[j][i]=max(mx[j-1][i],mx[j-1][i+Bin[j-1]]), mn[j][i]=min(mn[j-1][i],mn[j-1][i+Bin[j-1]]); } int mxRMQ(int x,int y) { int k=Log[y-x+1]; return max(mx[k][x],mx[k][y-Bin[k]+1]); } int mnRMQ(int x,int y) { int k=Log[y-x+1]; return min(mn[k][x],mn[k][y-Bin[k]+1]); } double stu1() { double ans=0; for(int j=L;j<=n;j++) { ans=max(ans,(double)(mxRMQ(j-L+1,j)-mnRMQ(j-L+1,j))/(L-1+K)); } return ans; }}namespace DD{ double em; namespace A { struct mnlist//单调减 { int head,tail,pos[maxn]; void clear(){head=1,tail=0;} void push_back(int x) { while(head<=tail&&(double)-a[pos[tail]]<=(double)-a[x]+em*(x-pos[tail]))tail--; pos[++tail]=x; } void pop_top(int lim){ while(head<=tail&&pos[head]<=lim)head++;} int top(){ return pos[head];} }A; bool check() { A.clear(); for(int j=L;j<=n;j++) { A.pop_top(j-R);//<=该决策点无效 A.push_back(j-L+1); int i=A.top(); if((double)(a[j]-a[i])+em*i>=em*(K+j))return true; } return false; } } //~~~~~~~~~~~~~~A~~~~~~~~~~~~~~~~~~~~ namespace B { struct mxlist { int head,tail,pos[maxn]; void clear(){head=1,tail=0;} void push_back(int x) { while(head<=tail&&(double)a[pos[tail]]<=(double)a[x]+em*(x-pos[tail]))tail--; pos[++tail]=x; } void pop_top(int lim){ while(head<=tail&&pos[head]<=lim)head++;} int top(){ return pos[head];} }B; bool check() { B.clear(); for(int j=L;j<=n;j++) { B.pop_top(j-R);//<=该决策点无效 B.push_back(j-L+1); int i=B.top(); if((double)(a[i]-a[j])+em*i>=em*(K+j))return true; } return false; } } //~~~~~~~~~~~~~~B~~~~~~~~~~~~~~~~~~~~ bool check(){ return A::check()|B::check();} double stu2() { double el=0,er=1e8; while(er-el>1e-5) { em=(el+er)/2; if(check())el=em; else er=em; } return el; }}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d%d%d%d",&n,&K,&L,&R); for(int i=1;i<=n;i++)scanf("%d",&a[i]); ST::main(); printf("%.4lf\n",max(ST::stu1(),DD::stu2())); } return 0;}