题目的意思很简单,给出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
![](/Images/OutliningIndicators/None.gif)
#include <stdio.h>
![](/Images/OutliningIndicators/None.gif)
typedef struct
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int x,y;
}node;
node queue[100010],tmp;
int head,tail;
![](/Images/OutliningIndicators/None.gif)
double res;
![](/Images/OutliningIndicators/None.gif)
int N,K,sum[100010];
![](/Images/OutliningIndicators/None.gif)
double max(double a,double b)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
if(a > b)
return a;
return b;
}
![](/Images/OutliningIndicators/None.gif)
long long xmul(node a,node b,node c)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
return (long long)(c.y-a.y)*(b.x-a.x) - (long long)(b.y - a.y)*(c.x - a.x) ;
}
![](/Images/OutliningIndicators/None.gif)
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i;
while(scanf("%d%d",&N,&K)!=EOF)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
sum[0] = 0;
for(i=1;i<=N;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d",&sum[i]);
sum[i] += sum[i-1];
}
head = tail = 0;
res = 0.0;
for(i=K;i<=N;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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;
}
![](/Images/OutliningIndicators/None.gif)