題目的意思很簡單，給出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;
}