Luogu

分析

先把长度为 $L$ 时的答案算出来,则剩下的情况中仅有最小值、最大值分别在两端点的区间可能成为答案。

为了方便,只考虑最小值在左端点的情况,另一种情况类似。

既然是分数规划,二分答案 $mid$,check() 时需要判定

$$ (a_j-mid\times j)-(a_i-mid\times i)\geq k\times mid,\quad j-i+1\in(L,R] $$

单调队列求出左边的最大值即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
 
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;

int n,k,l,r,a[N];

int f[17][N],g[17][N],lg[N];
inline void buildST() {
    for (re int i=1;i<=n;++i) f[0][i]=g[0][i]=a[i];
    for (re int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
    for (re int i=1;i<17;++i)
        for (re int j=1;j+(1<<i)-1<=n;++j) {
            f[i][j]=max(f[i-1][j],f[i-1][j+(1<<(i-1))]);
            g[i][j]=min(g[i-1][j],g[i-1][j+(1<<(i-1))]);
        }
}
inline int qmax(int l,int r) {
    int t=lg[r-l+1];
    return max(f[t][l],f[t][r-(1<<t)+1]);
}
inline int qmin(int l,int r) {
    int t=lg[r-l+1];
    return min(g[t][l],g[t][r-(1<<t)+1]);
}

int h,t,Q[N]; double b[N];
inline double calc(double mid) {
    for (re int i=1;i<=n;++i) b[i]=a[i]-mid*i;
    h=1,t=0;
    for (re int i=1;i+l<=n;++i) {
        while (h<=t&&i+l-Q[h]+1>r) ++h;
        while (h<=t&&b[Q[t]]>=b[i]) --t;
        Q[++t]=i;
        if (b[i+l]-b[Q[h]]>=mid*k) return 1;
    }
    return 0;
}

inline int check(double mid) {
    if (calc(mid)) return 1;
    reverse(a+1,a+n+1);
    if (calc(mid)) return 1;
    return 0;
}

int main() {
    int T=read();
    while (T--) {
        n=read(),k=read(),l=read(),r=read();
        for (re int i=1;i<=n;++i) a[i]=read();
        buildST(); double ans=0;
        for (re int i=1;i+l-1<=n;++i)
            ans=max(ans,1.0*(qmax(i,i+l-1)-qmin(i,i+l-1))/(l-1+k));
        double L=0,R=1e3;
        while (R-L>1e-6) {
            double mid=(L+R)/2;
            if (check(mid)) L=mid;
            else R=mid;
        }
        printf("%.4lf\n",max(ans,L));
    }
    return 0;
}
最后修改:2020 年 02 月 27 日 09 : 43 AM