题目的意思很简单，给出N个正整数，求最大的，长度大于K的某一段的平均值。好吧，这句听起来有点拗口。数学表达式就是 Max(ave(i,j)) (j-i>=K)。
这题是去年百度之星第二场比赛的一道题，煞费苦心不会做，那时候看了论文也不会做。过了快一年了，今天终于把它A掉了。。。
首先，ave(i,j)可以变形为一个式子， ave(i,j) = (sum[j] - sum[i-1] ) / (j - i + 1) 。
这个式子要表达什么意思呢？表示j点到i点得斜率！如此神奇的想法。。。
变成斜率之后，问题远远没有得到解决。问题变成了给出N个点的坐标，求这N个点任意连线的最大斜率。最普通的办法:从前到后枚举N个点，再枚举前0到i-k个点，比较的出最大斜率。但是通过作图我们可以得出一个结论，对于三个点，a,b,c,如果ca的斜率比cb的大，那么以后任意一个点，到点b的斜率都不可能比到a和c的大。所以这时候要舍弃掉b点。所以在维护前面0,i-K个点得时候,如果出现了上述提到的情况，则删除点b,好了，这样复杂度最坏情况下还是N^2。我们继续想，当出现一个新的点得时候，真的要枚举前面所有的点吗？我们只要找到维护的点到当前点得切线就好了，这个可以用二分查找找出来，比较麻烦。最后一步神优化：当当前维护的点得前面的点不是最大斜率的时候，以后的点也不可能是最大斜率。这个自己证明去吧~
这个题煞费苦心的想了一天，明白怎么回事了，发现结论很简单。但是交到hdoj上的时候，TLE了。没耐心看了discuss，原来是scanf要自己写。不想写，百度代码，发现有个神人写了五十行的代码，未自己写输入，交，A之。原来是自己的代码太冗余了。于是便仿照他的写法，发现问题很简单，一切很明了~A之。代码如下：
//by bigrabbit
#include <stdio.h>
typedef struct
{
int x,y;
}node;
node queue[100010],tmp;
int head,tail;
double res;
int N,K,sum[100010];
double max(double a,double b)
{
if(a > b)
return a;
return b;
}
long long xmul(node a,node b,node c)
{
return (long long)(c.y-a.y)*(b.x-a.x) - (long long)(b.y - a.y)*(c.x - a.x) ;
}
int main()
{
int i;
while(scanf("%d%d",&N,&K)!=EOF)
{
sum[0] = 0;
for(i=1;i<=N;i++)
{
scanf("%d",&sum[i]);
sum[i] += sum[i-1];
}
head = tail = 0;
res = 0.0;
for(i=K;i<=N;i++)
{
tmp.x = i-K;
tmp.y = sum[i-K];
while(head - tail >= 2 && xmul(queue[head-2],queue[head-1],tmp) <= 0 )
head--;
queue[head++] = tmp;
node now;
now.x = i;now.y = sum[i];
while(head - tail >= 2 && xmul(queue[tail],queue[tail+1],now) >= 0 )
tail++;
res = max(res,(double)(sum[i] - queue[tail].y)/(double)(i - queue[tail].x));
}
printf("%.2f\n",res);
}
return 0;
}