NC20220. [JSOI2015]送礼物
描述
输入描述
本题每个测试点有多组数据。输入第一行包含一个正整数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
输入:
1 5 1 2 4 1 2 3 4 5
输出:
0.7500
C++11(clang++ 3.9) 解法, 执行用时: 337ms, 内存消耗: 1144K, 提交时间: 2019-03-09 18:15:53
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
typedef double f2;
#define eps 1e-7
#define N 50050
int n,a[N],K,L,R,Q1[N],l1,r1,Q2[N],l2,r2,Q3[N],l3,r3;
f2 t[N];
int main() {
int T;
scanf("%d",&T);
while(T--) {
scanf("%d%d%d%d",&n,&K,&L,&R);
int i;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
l1=r1=l2=r2=0;
for(i=1;i<L;i++) {
while(l1<r1&&a[Q1[r1-1]]>=a[i]) r1--;
while(l2<r2&&a[Q2[r2-1]]<=a[i]) r2--;
Q1[r1++]=Q2[r2++]=i;
}
f2 ans1=-1000;
for(i=L;i<=n;i++) {
while(l1<r1&&i-Q1[l1]>=L) l1++;
while(l2<r2&&i-Q2[l2]>=L) l2++;
while(l1<r1&&a[Q1[r1-1]]>=a[i]) r1--;
while(l2<r2&&a[Q2[r2-1]]<=a[i]) r2--;
Q1[r1++]=Q2[r2++]=i;
ans1=max(ans1,1.0*(a[Q2[l2]]-a[Q1[l1]])/(L-1+K));
}
f2 l=0,r=1000;
while(r-l>eps) {
f2 mid=(l+r)/2;
f2 re=-100000;
l3=r3=0;
for(i=1;i<=n;i++) t[i]=a[i]-i*mid;
for(i=L+1;i<=n;i++) {
while(l3<r3&&i-Q3[l3]>=R) l3++;
while(l3<r3&&t[Q3[r3-1]]>=t[i-L]) r3--;
Q3[r3++]=i-L; re=max(re,t[i]-t[Q3[l3]]);
}
l3=r3=0;
for(i=1;i<=n;i++) t[i]=a[i]+i*mid;
for(i=n-L;i;i--) {
while(l3<r3&&Q3[l3]-i>=R) l3++;
while(l3<r3&&t[Q3[r3-1]]>=t[i+L]) r3--;
Q3[r3++]=i+L; re=max(re,t[i]-t[Q3[l3]]);
}
if(re>=mid*K) l=mid;
else r=mid;
}
//printf("%.4f\n",ans1);
printf("%.4f\n",max(ans1,l));
}
}