首页 > 代码库 > hdu 2993 MAX Average Problem(斜率DP入门题)
hdu 2993 MAX Average Problem(斜率DP入门题)
题目链接:hdu 2993 MAX Average Problem
题意:
给一个长度为 n 的序列,找出长度 >= k 的平均值最大的连续子序列。
题解:
这题是论文的原题,请参照2004集训队论文《周源--浅谈数形结合思想在信息学竞赛中的应用》
这题输入有点大,要加读入优化才能过。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 5 int tot; 6 const int BUF=25000000; 7 char Buf[BUF],*buf=Buf; 8 inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;} 9 10 const int N=1e5+7; 11 int sum[N],Q[N],n,k; 12 13 inline int useless(int a,int b,int c) 14 { 15 return 1ll*(sum[c]-sum[b])*(b-a)<=1ll*(sum[b]-sum[a])*(c-b); 16 } 17 18 int main() 19 { 20 tot=fread(Buf,1,BUF,stdin); 21 while(1) 22 { 23 if(buf-Buf+1>=tot)break; 24 read(n),read(k); 25 F(i,1,n)read(sum[i]),sum[i]+=sum[i-1]; 26 int head=1,tail=0; 27 double ans=0; 28 F(i,k,n) 29 { 30 while(head<tail&&useless(Q[tail-1],Q[tail],i-k))tail--; 31 Q[++tail]=i-k; 32 while(head<tail&&useless(Q[head+1],Q[head],i))head++; 33 ans=max(ans,(sum[i]-sum[Q[head]])*1.0/(i-Q[head])); 34 } 35 printf("%.2f\n",ans); 36 } 37 return 0; 38 }
hdu 2993 MAX Average Problem(斜率DP入门题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。