更好的阅读体验

A. 自闭的序列

给一个长度为$n$的非负整数序列$A$。

求一个A的长度在$L,R$之间的连续子序列，并且他们所有元素的平均值最大。

你只要输出这个最大值就可以了。

输入格式

第一行包含三个整数$n,L,R$。

接下来一行$n$个数，表示序列A。

输出格式

包括一行一个实数表示答案，保留四位小数。

样例

样例一

input

3 2 3
6 2 8

output

5.3333

约定与限制

对于$20\%$ 的数据，满足 $1 \le n \le 200$。

对于$40\%$ 的数据，满足 $1 \le n \le 2 000$。

对于$100\%$ 的数据 ，满足 $1 \le n \le 20000,0\le a_i\le 10^9,1\le L\le R\le N$ 。

时间限制:1s

空间限制:128MB

解题报告

题意理解

找一段区间，要求区间长度$len\in[l,r]$，找到一个区间，使得它的平均值最大。

$40pts$思路

我们可以想到，首先$O(n)$枚举区间长度$len$，然后我们可以，在用$O(n)$的时间遍历区间的左端点$l$，此时区间就是$[l,l+len-1]$。

然后统计这个区间的平均值，在这里的,我们可以提前预处理出

$$ sum[i]=\sum\limits_{n=1} ^ N a_i $$

那么在这里

$$ [l,r]平均值=\frac{(sum[r]-sum[l-1])}{(r-l+1)} $$

如果你思路类似于下面这段代码，直接枚举左端点和右端点，你的得分将是$90pts$,。
因为数据太水了

代码如下

#include <bits/stdc++.h>
using namespace std;
const int N=2e4+10;
int n,l,r,a[N],sum[N];
inline void init()
{
    scanf("%d%d%d",&n,&l,&r);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
    double ans=0;
    for(int a=1; a<=n; a++)//左端点
        for(int b=a+l-1; b<=a+r-1 && b<=n; b++)//右端点
        {
            int cnt=sum[b]-sum[a-1];//统计这个区间的总和
            ans=max(ans,cnt*1.0/(b-a+1));//平均值选取最大
        }
    printf("%.4lf\n",ans);
}
signed main()
{
    init();
    return 0;
}

$100pts$思路

当我们看到这道题目，答案是个小数的时候，应该不难想到二分算法。

而本题之所以可以使用二分算法，是因为题目答案具有单调性质。

我们可以二分答案，判断是否存在一个平均值$\ge y$的区间，这样就可以找到最终答案。

因为，如果说答案是$x$，那么显然 $\forall y \le x$，都可以满足，因为最终答案的区间，他们平均值一定满足$\ge y$

那么我们接下来需要讨论，如何在$O(n)$的时间，判断是否有区间合法。

$$ 设len表示区间的长度 \\\\ len(a,b)表示区间[a,b]长度 $$

现在要求我们，找到一个$l \le len \le r$的区间，满足他的平均值要大于$y$

此时我们可以使用单调队列满足本题。

我们知道单调队列 拥有两大性质

1. 队列中的元素具有顺序
2. 队列中元素具有某种单调性质

如果说现在有两个区间。$[a,i],[b,i]$

此时满足$sum[a,i] \le sum[b,i] 而且 a \le b$

那么此时，我们应该选择$[b,i]$区间，而不是$[a,i]$区间。

因为$len(b,i) \le len(a,i) \quad \& \quad sum[b,i] \ge sum[a,i]$

那么此时，我们需要将单调队列的细节进行处理。

1. 队头表示什么？
   满足区间长度限制，而且在队列中，$sum[head,i]$最大
2. 队尾表示什么？
   满足区间长度限制，在队列中区间长度最短。
3. 从哪里进入队列?
   从队尾，因为此时元素和当前节点构成的区间最短。
4. 如何将一个元素从队列退出？
   队头元素，不满足区间长度限制，则删除。
   队尾元素，面对新来的节点，不满足上面所述的单调性质，则删除。
   从上所述，这就是我们的单调队列的处理。

#include <bits/stdc++.h>
using namespace std;
#define eps 1e-6
#define Sum(a,b) (sum[(b)]-sum[(a)-1])//计算区间[a,b]的和
const int N=2e4+20;
int n,l,r,q[N<<1];
double a[N],sum[N],L,R;
inline int check(double x)
{
    for(int i=1; i<=n; i++)
        sum[i]=sum[i-1]+(a[i]-x);//将每个元素减去平均值，那么原来要求转化为，找到一段区间，使其和>=0即可
    int head=1,tail=0;
    for(int i=l; i<=n; i++)//右端点枚举
    {
        while(head<=tail && Sum(q[tail],i)<=Sum(i-l+1,i))//[q[tail],i]的值小于[i-l+1,i]
            tail--;
        q[++tail]=i-l+1;//存储当前区间左端点
        while(head<=tail && (i-q[head]+1)>r)//删去区间长度>r的左端点
            head++;
        if (Sum(q[head],i)>=0)//此时这一段区间平均值大于等于x
            return 1;
    }
    return 0;
}
inline void init()
{
//  freopen("ff.in","r",stdin);
    scanf("%d%d%d",&n,&l,&r);
    for(int i=1; i<=n; i++)
        scanf("%lf",&a[i]),R=max(R,a[i]);
    while(R-L>eps)//实数的二分答案
    {
        double mid=(L+R)/2.0;
        if (check(mid))
            L=mid;
        else
            R=mid;
    }
    printf("%.4lf\n",R);
}
signed main()
{
    init();
    return 0;
}