HDU 2993 MAX Average Problem（斜率DP经典+输入输出外挂）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2993

题目大意：给出n,k，给定一个长度为n的序列，从其中找连续的长度大于等于k的子序列使得子序列中的平均值最小。

解题思路：斜率DP经典题，

详细分析见：

NOI2004年周源的论文《浅谈数形结合思想在信息学竞赛中的应用》

还有要注意要用输入输出外挂，不是getchar()版的，是fread()版的，第一次遇到这么变态的题目- -|||。

代码：

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<stdio.h>

 using namespace std;

 const int N=1e5+;

 int q[N],head,tail;

 long long sum[N];

 double Slope(int k,int j){

     return double(sum[j]-sum[k])/(j-k);

 }

 //输入输出外挂

 const int BUF=;

 char Buf[BUF],*buf=Buf;

 template <class T>

 inline void read(T &a){

     for(a=;*buf<;buf++);

     while(*buf>)

         a=a*+*buf++-;

 }

 int main(){

     int n,k;

     int tot=fread(Buf,,BUF,stdin);

     while(){

         if(buf-Buf+>=tot)break;

         read(n),read(k);

         for(int i=;i<=n;i++){

             read(sum[i]);

             sum[i]+=sum[i-];

         }

         double ans=;

         head=tail=;

         q[tail++]=;

         for(int i=k;i<=n;i++){

             while(head+<tail&&Slope(q[head],i)<=Slope(q[head+],i)){

                 head++;

             }

             ans=max(ans,Slope(q[head],i));

             int j=i-k+;

             while(head+<tail&&Slope(q[tail-],q[tail-])>=Slope(q[tail-],j)){

                 tail--;

             }

             q[tail++]=j;

         }

         printf("%.2f\n",ans);

     }

     return ;

 }