标签：二分，单调队列
题目描述
给定一个长度为n的序列a_i,定义a[i]为第i个元素的价值。现在需要找出序列中最有价值的“段落”。段落的定义是长度在[S,T]之间的连续序列。最有价值段落是指平均值最大的段落，
段落的平均值=段落总价值/段落长度。
输入输出格式
输入格式：
第一行一个整数n，表示序列长度。
第二行两个整数S和T，表示段落长度的范围，在[S,T]之间。
第三行到第n+2行，每行一个整数表示每个元素的价值指数。
输出格式：
一个实数，保留3位小数，表示最优段落的平均值。
输入输出样例
输入样例#1：
3
2 2
3
-1
2
输出样例#1：
1.000
说明
【数据范围】
对于30%的数据有n<=1000。
对于100%的数据有n<=100000,1<=S<=T<=n，-10000<=价值指数<=10000。
题意：给定长度为N的序列
求：max{(a[i]+a[i+1]+……+a[i+j])/j} s<=j<=t
看题的第一眼想到了单调队列，但是貌似会被卡掉TLE
正解是二分答案，判断每次的mid是否可行
Sum[i]表示前i个数减去过去mid的总和
对于第i个数，如果sum[i]>=min{sum[i-y]->sum[i-x]}那么当前方案可行
对于min{sum[i-y]~sum[i-x]}，我们用一个单调队列维护就行了
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const int maxn=1e5+6,inf=1e9;
int a[maxn],tt[maxn];
LL c[maxn],sum[maxn];
int n,i,l,r,x,y,mid,ans=0;
inline bool check(int k){
mem(c,0);mem(tt,0);
rep(i,1,n)sum[i]=sum[i-1]+a[i]-k;
int head=1,tail=0;
rep(i,1,n){
int j=i-x;
if(j<0)continue;
while((sum[j]<c[tail])&&(head<=tail))tail--;
c[++tail]=sum[j];
tt[tail]=j;
if(tt[head]<(i-y))head++;
if(sum[i]>=c[head])return true;
}
return false;
}
int main()
{
scanf("%d%d%d",&n,&x,&y);
rep(i,1,n)scanf("%d",&a[i]),a[i]*=1e4;
l=-inf;r=inf;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)){l=mid+1;ans=mid;}
else r=mid-1;
}
printf("%.3lf",ans/1e4);
return 0;
}
