題目的意思很簡單，給出N個(gè)正整數(shù)，求最大的，長度大于K的某一段的平均值。好吧，這句聽起來有點(diǎn)拗口。數(shù)學(xué)表達(dá)式就是 Max(ave(i,j)) (j-i>=K)。
這題是去年百度之星第二場比賽的一道題，煞費(fèi)苦心不會(huì)做，那時(shí)候看了論文也不會(huì)做。過了快一年了，今天終于把它A掉了。。。
首先，ave(i,j)可以變形為一個(gè)式子， ave(i,j) = (sum[j] - sum[i-1] ) / (j - i + 1) 。
這個(gè)式子要表達(dá)什么意思呢？表示j點(diǎn)到i點(diǎn)得斜率！如此神奇的想法。。。
變成斜率之后，問題遠(yuǎn)遠(yuǎn)沒有得到解決。問題變成了給出N個(gè)點(diǎn)的坐標(biāo)，求這N個(gè)點(diǎn)任意連線的最大斜率。最普通的辦法:從前到后枚舉N個(gè)點(diǎn)，再枚舉前0到i-k個(gè)點(diǎn)，比較的出最大斜率。但是通過作圖我們可以得出一個(gè)結(jié)論，對于三個(gè)點(diǎn)，a,b,c,如果ca的斜率比cb的大，那么以后任意一個(gè)點(diǎn)，到點(diǎn)b的斜率都不可能比到a和c的大。所以這時(shí)候要舍棄掉b點(diǎn)。所以在維護(hù)前面0,i-K個(gè)點(diǎn)得時(shí)候,如果出現(xiàn)了上述提到的情況，則刪除點(diǎn)b,好了，這樣復(fù)雜度最壞情況下還是N^2。我們繼續(xù)想，當(dāng)出現(xiàn)一個(gè)新的點(diǎn)得時(shí)候，真的要枚舉前面所有的點(diǎn)嗎？我們只要找到維護(hù)的點(diǎn)到當(dāng)前點(diǎn)得切線就好了，這個(gè)可以用二分查找找出來，比較麻煩。最后一步神優(yōu)化：當(dāng)當(dāng)前維護(hù)的點(diǎn)得前面的點(diǎn)不是最大斜率的時(shí)候，以后的點(diǎn)也不可能是最大斜率。這個(gè)自己證明去吧~
這個(gè)題煞費(fèi)苦心的想了一天，明白怎么回事了，發(fā)現(xiàn)結(jié)論很簡單。但是交到hdoj上的時(shí)候，TLE了。沒耐心看了discuss，原來是scanf要自己寫。不想寫，百度代碼，發(fā)現(xiàn)有個(gè)神人寫了五十行的代碼，未自己寫輸入，交，A之。原來是自己的代碼太冗余了。于是便仿照他的寫法，發(fā)現(xiàn)問題很簡單，一切很明了~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;
}