其他学习笔记
这题真是凝聚了很多精华，那么我们就介绍这题的四兄弟：
-
大哥 平均数 这道题是其他兄弟的基础。
-
二哥 Best Cow 这位更是重量级，因为没特长只能强大哥的外貌，会大哥即识二哥。
-
三哥 PROSJEK 这位哥看似有点创新却仍没逃过一家子的基因，只是变为了小数运算。
-
四哥 寻找段落 作为我们压轴哥必须有牌面，但是却因此犯下了贪婪之罪，想包含所有的弟兄的特点来成为绿题，看似他是成功了，但也导致了他的
臭名昭著
而今天我们就要解析这个四哥，题意是找一个长度为 \(s\) 到 \(t\) 之间的区间使区间平均值最大。
看数据范围 \(n\le 1e5\)，可以分析一下什么复杂度的算法能实现（感觉分析一下是很有意义的），首先 \(n^2\) 肯定不行，那常见的还有 \(O(n)\) 和 \(O(n\log n)\) 常见吗？ ，感觉可以采用第二个复杂度，那带 \(\log\) 的算法那不直接就是二分 （分治） 。
一般求什么二分什么，我们直接就二分平均值答案，注意这题可能会有负数，而且答案是浮点数，我们就要用负数浮点数二分答案，如何实现下看代码或看学习笔记，然后将这个平均数带入函数判断是否合法，如果合法调大，反之调小。
函数首先求了个前缀和并减去平均值得到一个 \(sum[]\)，接着用一个单调队列使得 \(l\) 指向 \(sum\) 值最大的下标，如果目前遍历到的点的 \(sum_i - sum_l\) 的值大于 \(0\) 代表这个区间假设平均值是合法，然后调整 \(l\) 反复直到到达边界。
下见代码：
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
const double eps=1e-6;
double sum[N];
int a[N];
int q[N];
int n,m;
int s,t;
int check(double mid){
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i]-mid;
}
int l=1,r=0;
for(int i=1;i<=n;i++){
if(i>=s){
while(r>=l&&sum[i-s]<sum[q[r]]){
r--;
}
q[++r]=i-s;
}
if(l<=r&&q[l]<i-t){
l++;
}
if(l<=r&&sum[i]-sum[q[l]]>=0){
return 1;
}
}
return 0;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>s>>t;
for(int i=1;i<=n;i++){
cin>>a[i];
}
double l=-1e4-1,r=1e4+1;
while(l+eps<r){
double mid=(l+r)/2;
if(check(mid)){
l=mid;
}
else{
r=mid;
}
}
printf("%.3lf",l);
return 0;
}