**题目，出题人说的什么G2玩意

还是有收获的

目前的斜率dp问题大致分为两类
1.总结公式后，进行线性规划求解
2.数形结合，与凸包相似。

本题属于第二种。
我们可以求一个前缀和。
然后我们可以知到，对于目前的节点j
其实就是在0->j-k中找一个点，使得(sum[j]-sum[i])/(j-i)最大。
我们如果硬是用dp的话，那么就是n^2级。
很明显这个形式让我们想到了斜率优化。
首先我们维护的是一个下凸包。
为什么是这样的呢？建议看这篇博客的分析，他对斜率dp的凸包分析方法，我觉得十分有用，精辟！！！！
那么我们就维护下凸包就行了。
关键的第二弹：
如何在O(1)的时间内得到答案？
在上面的博客中，他说可以通过斜率的比较pop前面的点。因为他们一定不是后面dp的答案。
但是我认为这是错的。其实还是有可能是后面的最有答案的，
但是一定不会是全局的最优答案了。所以被我们pop掉了。

#include<iostream>
#include<algorithm>
using namespace std;
const int max_n = 1e5+100;
//输入外挂
int tottt;
const int BUF=25000000;
char Buf[BUF],*buf=Buf;
inline void read(int &a){
    for(a=0;*buf<48;buf++);
    while(*buf>47) a=a*10+*buf++-48;
}
int a[max_n];
int n,k;
int que[max_n<<1];
int ql,qr;
double geth(int x1,int x2){
    return (1.0*a[x1]-1.0*a[x2])/(1.0*x1-1.0*x2);
}
int main(){
    tottt=fread(Buf,1,BUF,stdin);
    while (1){
        if(buf-Buf+1>=tottt)break;
        read(n);read(k);
        ql=qr=1;
        for (int i=1;i<=n;++i)read(a[i]);
        for (int i=1;i<=n;++i)a[i]+=a[i-1];
        double ans = 1.0*a[k]/1.0*k;
        que[qr++]=0;
        for (int i=k+1;i<=n;++i){
            int p = i-k;int pn = i;
            while (qr-ql>=2&&geth(que[qr-2],que[qr-1])>=geth(que[qr-1],p))--qr;
            que[qr++]=p;
            while (qr-ql>=2&&geth(que[ql],que[ql+1])<=geth(que[ql+1],pn))++ql;
            ans = max(ans,geth(que[ql],pn));
        }printf("%.2lf\n",ans);
    }
}

顺便收获了一个输入外挂