[Jsoi2015]送礼物

时间限制:30s      空间限制:512MB

题目描述

JYY和CX的结婚纪念日即将到来,JYY来到萌萌开的礼品店选购纪念礼物。
萌萌的礼品店很神奇,所有出售的礼物都按照特定的顺序都排成一列,而且相邻
的礼物之间有一种神秘的美感。于是,JYY决定从中挑选连续的一些礼物,但究
竟选哪些呢?
【问题描述】
假设礼品店一共有N件礼物排成一列,每件礼物都有它的美观度。排在第i
1< =i< =N个位置的礼物美观度为正整数Ai,。JYY决定选出其中连续的一段,
即编号为礼物i,i+1,…,j-1,j的礼物。选出这些礼物的美观程度定义为
(M(i,j)-m(i,j))/(j-i+k)
其中M(i,j)表示max{Ai,Ai+1....Aj},m(i,j)表示min{Ai,Ai+1....Aj},K为给定的正整数。
由于不能显得太小气,所以JYY所选礼物的件数最少为L件;同时,选得太
多也不好拿,因此礼物最多选R件。JYY应该如何选择,才能得到最大的美观程
度?由于礼物实在太多挑花眼,JYY打算把这个问题交给会编程的你。


输入格式

本题每个测试点有多组数据。输入第一行包含一个正整数T(T< =10),表示
有T组数据。
每组数据包含两行,第一行四个非负整数N,K,L,R(2< =L< =R< =N。第二行
包含N个正整数,依次表示A1,A2....An,(Ai< =10^8),N,K< = 50,000


输出格式

输出T行,每行一个非负实数,依次对应每组数据的答案,数据保证答案不
会超过10^3。输出四舍五入保留4位小数。


样例输入

1
5 1 2 4
1 2 3 4 5

样例输出

0.7500 

提示

没有写明提示


题目来源

By 佚名上传