题解 P6087 【[JSOI2015]送礼物】

· · 题解

题目

题目链接

分析

单调队列加 01 分数规划好题！（前几天刚刚学的 01 分数规划）。

首先看到题目中的一个极其熟悉的柿子和要求的最大值，那么这个题肯定就与 01 分数规划有关了，毫无疑问。

我们先从题意入手，它的意思就是让我们选出一段区间，让区间最大值和最小值的差除以区间长度减一加上 k 的最大值。也就是题目中给的式子：

\frac{M(i,j) \ -\ m(i,j)}{j-i+k}

当然区间长度是有限制的，长度从 L 到 R。

情况一

接下来我们根据这个题要求的答案入手，要求的是一个分数的最大值，那么我们要做的就是让分子尽量大或者分母尽量小。

因为每个区间的最大和最小值都是确定好了的，那么如果当前区间的最大值或最小值在区间内部，那么长度可以缩小的，最优状态就是区间的两个边界分别为最大和最小值。

我们设 a[i] 数组表示每个位置的值，区间从 l 到 r ，当前二分到的答案为 mid ，那么我们就得到了这样的式子：

\frac{a[r] - a[l]}{r-l+k}\geqslant mid

因为最大值和最小值的位置可以交换，那么上式中 r 和 l 可以互换。所以我们对式子分母乘过去，然后移项得到了两个式子：

(a[l]+l\times mid)-(a[r]+r\times mid)\geqslant k\times mid (a[l]-l\times mid)-(a[r]-r\times mid)\geqslant k\times mid

而这不就是得到了 01 分数规划中的那个式子了吗。我们只需要利用一个 c[i] 数组记录 a[i]+i 和 a[i]-i 两种，然后用单调队列分别维护最大值，最后判断一下是否满足上边的那两个式子，继续进行二分即可。

情况二

某个区间中的最小和最大值之间距离比 L 小，那么为了取最优解，就可以直接让长度等于 L ，这样肯定是最优的，我们只需要用两个单调队列维护区间最大和最小值就可以算出答案了，最后只需要用这个算出来的答案跟二分出来的答案比较大小选大的就行了。

具体细节代码中注释见：

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 5e5+10;
const double eps = 1e-6;
double a[maxn];
double c[maxn];
int head1,head2,tail1,tail2;
int q1[maxn],q2[maxn];
int n,k,L,R;
int q3[maxn];
inline int read(){//快读
    int s = 0,f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}
bool jud(double mid){//二分判断函数
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;++i){//记录第一种相减的情况
        c[i] = a[i] - i * mid;
    }
    double ans = -100000.0;
    int head3=0,tail3=0;
    for(int i=L+1;i<=n;++i){//单调队列维护最大值
        while(head3 < tail3 && i - q3[head3] >= R)head3++;
        while(head3 < tail3 && c[q3[tail3-1]] >= c[i-L])tail3--;
        q3[tail3++] = i-L;//记录最小值的位置
        ans = max(ans,c[i] - c[q3[head3]]);
    }
    head3=0,tail3=0;
    for(int i=1;i<=n;++i){//找另一种相加的情况
        c[i] = a[i] + i * mid;
    }
    for(int i=n-L;i;--i){//单调队列维护最大值
        while(head3 < tail3 && i - q3[head3] >= R)head3++;
        while(head3 < tail3 && c[q3[tail3-1]] >= c[i+L])tail3--;
        q3[tail3++] = i+L;
        ans = max(ans,c[i] - c[q3[head3]]);
    }
    return ans - mid * k >= 0;//判断是否成立
}
double calc1(){//计算长度为L的情况下的答案
    double ans = -100000.0;
    head1 = head2 = tail1 = tail2 = 0;//一定要初始化，不然爆掉
    for(int i=1;i<=n;++i){
        if(i < L){//位置不超过L的时候只维护单调性
            while(head1 < tail1 && a[q1[tail1-1]] >= a[i])tail1--;
            while(head2 < tail2 && a[q2[tail2-1]] <= a[i])tail2--;
        }
        else {//位置超过L的时候维护单调性且长度超过L的时候弹出队首
            while(head1 < tail1 && i - q1[head1] >= L)head1++;
            while(head2 < tail2 && i - q2[head2] >= L)head2++;
            while(head1 < tail1 && a[q1[tail1-1]] >= a[i])tail1--;
            while(head2 < tail2 && a[q2[tail2-1]] <= a[i])tail2--;
        }
        q1[tail1++] = i;
        q2[tail2++] = i;
        if(i >= L)//算答案
            ans = max(ans,(double)(a[q2[head2]] - a[q1[head1]]) / (L-1+k));
    }
    return ans;
}
int main(){
    int T = read();
    while(T--){
        n = read();
        k = read();
        L = read();
        R = read();
        for(int i=1;i<=n;++i){
            scanf("%lf",&a[i]);
        }
        double ans = calc1();//长度刚好为L的答案
        double l = 0,r = 1000000.0;
        while(r - l >= eps){//二分找到最优解
            double mid = (l + r) / 2;
            if(jud(mid))l = mid;
            else r = mid;
        }
        printf("%.4lf\n",max(ans,l));//取两种情况的最大值
    }
    return 0;
}