MAX Average Problem

论文题，再度认识了数形结合！！！所谓斜率判断时，可以划分阴影区域的，有助于判断

#include<iostream>
#include<algorithm>
#include<queue>
#include<deque>
#include<vector>
#include<functional>
using namespace std;
inline int read(){
    char c=getchar();
    int x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
const int max_n = 1e5+100;
int a[max_n];
double sum[max_n];
int n,k;
double fix(int i,int j){
    return (sum[i]-sum[j])/(i-j);
}
bool check(int a,int b,int c){
    return fix(a,c)<=fix(b,c);
}
bool check2(int a,int b,int c){
    return fix(a,c)<=fix(a,b);
}
int main(){
    while (~scanf("%d %d",&n,&k)){
        for (int i=1;i<=n;++i)a[i]=read();
        for (int i=1;i<=n;++i)sum[i]=sum[i-1]+(double)a[i];
        deque<int> que;
        double ans = 0;
        for (int i=k;i<=n;++i){
            while (que.size()>=2&&check2(que[que.size()-1],que[que.size()-2],i-k))
                que.pop_back();
            que.push_back(i-k);
            while (que.size()>=2&&check(que[0],que[1],i))
                que.pop_front();
            ans = max(ans,fix(i,que.front()));
        }printf("%.2lf\n",ans);
    }
}