3176: 送礼物 [gift]（day1-2）
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 0 Solved: 0
[Status] [Submit] [Creator:]
Description
【故事背景】
JYY和CX的结婚纪念日即将到来，JYY来到萌萌开的礼品店选购纪念礼物。萌萌的礼品店很神奇，所有出售的礼物都按照特定的顺序都排成一列，而且相邻的礼物之间有一种神秘的美感。于是，JYY 决定从中挑选连续的一些礼物，但究竟选哪些呢？
【问题描述】
假设礼品店一共有n件礼物排成一列，每件礼物都有它的美观度。排在第i(1 ≤ i ≤ n)个位置的礼物美观度为 正整数 ai 。JYY 决定选出其中 连续 的一段，即编号为礼物i,i + 1,…,j− 1,j的礼物。选出这些礼物的美观程度定义为
其中M(i,j)表示max{ai,ai+1 ,…,aj}，m(i,j)表示min{ai,ai+1,…,aj}，K为给定的正整数 。
由于不能显得太小气，所以 JYY 所选礼物的件数最少为L件 ；同时，选得太多也不好拿，因此礼物最多选R件 。JYY 应该如何选择，才能得到最大的美观程度？由于礼物实在太多挑花眼，JYY 打算把这个问题交给会编程的你。
JYY和CX的结婚纪念日即将到来，JYY来到萌萌开的礼品店选购纪念礼物。萌萌的礼品店很神奇，所有出售的礼物都按照特定的顺序都排成一列，而且相邻的礼物之间有一种神秘的美感。于是，JYY 决定从中挑选连续的一些礼物，但究竟选哪些呢？
【问题描述】
假设礼品店一共有n件礼物排成一列，每件礼物都有它的美观度。排在第i(1 ≤ i ≤ n)个位置的礼物美观度为 正整数 ai 。JYY 决定选出其中 连续 的一段，即编号为礼物i,i + 1,…,j− 1,j的礼物。选出这些礼物的美观程度定义为
其中M(i,j)表示max{ai,ai+1 ,…,aj}，m(i,j)表示min{ai,ai+1,…,aj}，K为给定的正整数 。
由于不能显得太小气，所以 JYY 所选礼物的件数最少为L件 ；同时，选得太多也不好拿，因此礼物最多选R件 。JYY 应该如何选择，才能得到最大的美观程度？由于礼物实在太多挑花眼，JYY 打算把这个问题交给会编程的你。
Input
本题每个测试点有多组数据 。输入第一行包含一个正整数T(T ≤ 10) ，表示有T组数据。
每组数据包含两行，第一行四个非负整数n,K,L,R(2 ≤ L≤ R ≤ n 。第二行包含n个正整数，依次表示a1,a2 ,…,an(ai≤ 10^8)。
每组数据包含两行，第一行四个非负整数n,K,L,R(2 ≤ L≤ R ≤ n 。第二行包含n个正整数，依次表示a1,a2 ,…,an(ai≤ 10^8)。
Output
输出T行，每行一个非负实数，依次对应每组数据的答案，数据保证答案不会超过10^3 。输出四舍五入保留4位小数。
Sample Input Copy
1
5 1 2 4
1 2 3 4 5
Sample Output Copy
0.7500
HINT
【数据规模与约定】
对于20%的数据满足n ≤ 1,000；
对于10%的数据满足K = 0, L = 2, R = n；
对于10%的数据满足K = 1；
对于100%的数据满足n,K ≤ 50,000。
对于20%的数据满足n ≤ 1,000；
对于10%的数据满足K = 0, L = 2, R = n；
对于10%的数据满足K = 1；
对于100%的数据满足n,K ≤ 50,000。