hdu 2993 MAX Average Problem(斜率DP入门题)

题目链接:hdu 2993 MAX Average Problem

题意:

给一个长度为 n 的序列,找出长度 >= k 的平均值最大的连续子序列。

题解:

这题是论文的原题,请参照2004集训队论文《周源--浅谈数形结合思想在信息学竞赛中的应用》

这题输入有点大,要加读入优化才能过。

 #include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std; int tot;
const int BUF=;
char Buf[BUF],*buf=Buf;
inline void read(int&a){for(a=;*buf<;buf++);while(*buf>)a=a*+*buf++-;} const int N=1e5+;
int sum[N],Q[N],n,k; inline int useless(int a,int b,int c)
{
return 1ll*(sum[c]-sum[b])*(b-a)<=1ll*(sum[b]-sum[a])*(c-b);
} int main()
{
tot=fread(Buf,,BUF,stdin);
while()
{
if(buf-Buf+>=tot)break;
read(n),read(k);
F(i,,n)read(sum[i]),sum[i]+=sum[i-];
int head=,tail=;
double ans=;
F(i,k,n)
{
while(head<tail&&useless(Q[tail-],Q[tail],i-k))tail--;
Q[++tail]=i-k;
while(head<tail&&useless(Q[head+],Q[head],i))head++;
ans=max(ans,(sum[i]-sum[Q[head]])*1.0/(i-Q[head]));
}
printf("%.2f\n",ans);
}
return ;
}
上一篇:bzoj1002:[FJOI2007]轮状病毒


下一篇:hdu 5532 Almost Sorted Array(模拟)