题意：

各一个n(\(\le 20000\))的序列，定义纯洁序列为长度len满足\(L \le len \le R\)的序列，纯洁值为某一纯洁序列的平局值，输出所有纯洁序列中最大平均值。

分析：

二分 + 单调队列：二分出平均值mid, 下面来判断该平均值是否符合加大L的要求：

当mid偏小时：\(\sum{(a_i - mid)} >= \sum{(a_j - mid)} (i - r + 1 <= j <= i - l + 1)\)

若\(min\{ \sum(a_j - mid) (i - r + 1 <= j <= i - l + 1)\} <= \sum{a_i - mid}\)那么就肯定满足了。

即要求指定区间中的最小值，直接单调队列。\(O(nlogn)\)

code:

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

#include<ctime>

#include<deque>

using namespace std;

namespace IO {

    template<typename T>

    inline void read(T &x) {

        T i = 0, f = 1;

        char ch = getchar();

        for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());

        if(ch == '-') f = -1, ch = getchar();

        for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');

        x = i * f;

    }

    template<typename T>

    inline void wr(T x) {

        if(x < 0) putchar('-'), x = -x;

        if(x > 9) wr(x / 10);

        putchar(x % 10 + '0');

    }

}using namespace IO;

const int N = 2e4 + 5;

#define eps 1e-8

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

typedef long long ll;

double sum[N], ans;

deque<double> que;

inline bool calc(double mid){

    sum[0] = 0;

    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + 1.0 * a[i] - mid;

    que.clear();

    for(int i = l; i <= n; i++){

        while(!que.empty() && sum[(int)que.back()] >= sum[i - l]) que.pop_back();

        que.push_back(i - l);

        while(!que.empty() && i - que.front() > r) que.pop_front();

        if(!que.empty() && sum[i] >= sum[(int)que.front()]) return true;

    }

    return false;

}

int main(){

    freopen("h.in", "r", stdin);

    read(n), read(l), read(r);

    for(int i = 1; i <= n; i++) read(a[i]);

    double L = 0, R = 1e6;

    for(int t = 1; t <= 50; t++){

        double mid = (L + R) / 2;

        if(calc(mid)) L = mid;

        else R = mid;

    }

    printf("%.4f", L);

    return 0;

}