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,0le a_ile 10^9,1le Lle Rle N) 。
时间限制:1s
空间限制:128MB
解题报告
题意理解
找一段区间，要求区间长度(lenin[l,r])，找到一个区间，使得它的平均值最大。
(40pts)思路
我们可以想到，首先(O(n))枚举区间长度(len)，然后我们可以，在用(O(n))的时间遍历区间的左端点(l)，此时区间就是([l,l+len-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
",ans);
}
signed main()
{
init();
return 0;
}
(100pts)思路
当我们看到这道题目，答案是个小数的时候，应该不难想到二分算法。
而本题之所以可以使用二分算法，是因为题目答案具有单调性质。
我们可以二分答案，判断是否存在一个平均值(ge y)的区间，这样就可以找到最终答案。
因为，如果说答案是(x)，那么显然 (forall y le x)，都可以满足，因为最终答案的区间，他们平均值一定满足(ge y)
那么我们接下来需要讨论，如何在(O(n))的时间，判断是否有区间合法。
现在要求我们，找到一个(l le len le r)的区间，满足他的平均值要大于(y)
此时我们可以使用单调队列满足本题。
我们知道单调队列 拥有两大性质
- 队列中的元素具有顺序
- 队列中元素具有某种单调性质
如果说现在有两个区间。([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])
那么此时，我们需要将单调队列的细节进行处理。
- 队头表示什么？
满足区间长度限制，而且在队列中，(sum[head,i])最大 - 队尾表示什么？
满足区间长度限制，在队列中区间长度最短。 - 从哪里进入队列?
从队尾，因为此时元素和当前节点构成的区间最短。 - 如何将一个元素从队列退出？
队头元素，不满足区间长度限制，则删除。
队尾元素，面对新来的节点，不满足上面所述的单调性质，则删除。
从上所述，这就是我们的单调队列的处理。
#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
",R);
}
signed main()
{
init();
return 0;
}