题解：P6087 [JSOI2015] 送礼物

LovevoL · 2026-11-10 21:51:31 · 题解

分数规划问题，考虑二分答案 mid，问题即需要验证是否存在 l,r 使得：

\frac{\max_{i=l}^r A_i - \min_{i=l}^r A_i}{r-l+K} \ge mid

先对式子变形得到：

\max_{i=l}^r A_i - \min_{i=l}^r A_i \ge mid\times (r-l+K)

考虑枚举左端点 l，设最优右端点为 r。

设 [l,l+L-1] 的最大值为 mx，最小值为 mi；设 [l,l+R-1] 的最大值为 Mx，最小值为 Mi。那么如果 [l,l+L-1] 是有用的，就一定有 Mx=mx 或者 Mi=mi，否则左端点向右移动不会使得答案更劣。

这其实就是在说，[i+L,r] 这个区间对于整个区间 [l,r] 只会贡献 1 个最值。

接着有：若 r>i+L-1，则 A_r 一定是 [l,r] 的一个最值，因为如果不是最值，r 向左移显然不会更劣。

考虑按照 r 是区间 [l,r] 的最大值还是最小值分开讨论：

$$ A_r-\min_{i=l}^{i+L-1} A_i \ge mid\times (r-l+K) $$ 这里最小值可以取 $\min_{i=l}^{i+L-1} A_i$ 的原因就是我们上面说的 $[i,i+L-1]$ 至少贡献一个最值，否则答案不会是最优的。对这个式子稍微变形得到： $$ A_r -mid\times r \ge mid\times (K-l)+\min_{i=l}^{i+L-1} A_i $$ 于是我们维护 $\max_{i=i+L}^{i+R-1} \{A_i-mid\times i\}$ 即可。
$$ - A_r \ge mid\times (r-l+K) - \max_{i=l}^r A_i $$ 同上，对式子稍微变形得到： $$ - A_r - mid\times r \ge mid\times (K-l) - \max_{i=l}^r A_i $$ 维护 $\max_{i=i+L}^{i+R-1}\{ -A_i-mid\times i \}$ 即可。

两个区间 \max 滑动窗口即可维护，单次 \text{check} 复杂度 O(n)，总复杂度 O(Tn\log V)。

:::success[Code] 需要注意一些边界问题。

#include<bits/stdc++.h>
#define int long long 
#define YUANSHEN ios_base::sync_with_stdio(0);
#define QIDONG cin.tie(0);
#define inf 1e3
#define endl '\n'
#define mod 998244353
#define frein freopen("check.in","r",stdin);
#define freout freopen("me.out","w",stdout);
#define pii pair<int,int>
#define double long double
using namespace std;
const int maxn=1e6+10;
const double eps=1e-7;

int T,a[maxn],n,k,L,R,q[maxn],head,tail;

double mi[maxn],mx[maxn];

struct ST_table{
    int st_min[maxn][20],st_max[maxn][20],lg[maxn];
    void init(){
        for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
        for(int i=1;i<=n;i++)st_min[i][0]=st_max[i][0]=a[i];
        for(int j=1;j<=19;j++)
            for(int i=1;i+(1<<j)-1<=n;i++)
                st_max[i][j]=max(st_max[i][j-1],st_max[i+(1<<(j-1))][j-1]),
                st_min[i][j]=min(st_min[i][j-1],st_min[i+(1<<(j-1))][j-1]);
    }
    int QueryMin(int l,int r){return min(st_min[l][lg[r-l+1]],st_min[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);}
    int QueryMax(int l,int r){return max(st_max[l][lg[r-l+1]],st_max[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);}
}St;

void Init(double mid){
    head=1,tail=0;
    for(int i=L+1;i<=min(R,n);q[++tail]=i,i++)
        while(head<=tail&&1.0*a[q[tail]]+1.0*mid*q[tail]>1.0*a[i]+1.0*mid*i)tail--;
    for(int i=1;i+L<=n;i++){
        while(head<=tail&&q[head]<i+L)head++;
        mi[i]=a[q[head]]+1.0*mid*q[head];
        if(i+R<=n){
            while(head<=tail&&1.0*a[q[tail]]+1.0*mid*q[tail]>1.0*a[i+R]+1.0*mid*(i+R))tail--;
            q[++tail]=i+R;
        }
    }
    head=1,tail=0;
    for(int i=L+1;i<=min(R,n);q[++tail]=i,i++)
        while(head<=tail&&1.0*a[q[tail]]-1.0*mid*q[tail]<1.0*a[i]-1.0*mid*i)tail--;
    for(int i=1;i+L<=n;i++){
        while(head<=tail&&q[head]<i+L)head++;
        mx[i]=a[q[head]]-1.0*mid*q[head];
        if(i+R<=n){
            while(head<=tail&&1.0*a[q[tail]]-1.0*mid*q[tail]<1.0*a[i+R]-1.0*mid*(i+R))tail--;
            q[++tail]=i+R;
        }
    }
}

bool check(double mid){
    if(L==R){
        for(int i=1;i+L<=n;i++){
            int MI=St.QueryMin(i,i+L-1),
                MX=St.QueryMax(i,i+L-1);
            if(MX-MI>=mid*1.0*(L-1+k))return true;
        }
        int Mi=St.QueryMin(n-L+1,n),
        Mx=St.QueryMax(n-L+1,n);
        if(Mx-Mi>=mid*1.0*(L-1+k))return true;
        return false;
    }
    Init(mid);
    for(int i=1;i+L<=n;i++){
        int MI=St.QueryMin(i,i+L-1),MX=St.QueryMax(i,i+L-1);
        if(MX-MI>=mid*1.0*(L-1+k))return true;
        if(mx[i]-MI+1.0*mid*(i+L-1)>=1.0*mid*(L-1+k))return true;
        if(MX-mi[i]+1.0*mid*(i+L-1)>=1.0*mid*(L-1+k))return true;
    } 
    int Mi=St.QueryMin(n-L+1,n),Mx=St.QueryMax(n-L+1,n);
    if(Mx-Mi>=mid*1.0*(L-1+k))return true;
    return false;
}

void Solve(){
    cin>>n>>k>>L>>R;
    for(int i=1;i<=n;i++)cin>>a[i];
    St.init();
    double l=0,r=inf,ans=0;
    while(l+eps<=r){
        double mid=(l+r)/2;
        if(check(mid))l=mid,ans=mid;
        else r=mid;
    }cout<<fixed<<setprecision(4)<<ans+eps<<endl;
}

signed main(){
    YUANSHEN QIDONG
//  frein freout
    cin>>T;
    while(T--)Solve();
    return 0;
}

:::