这道题算是给斜率优化dp打下一个基础。题目要求的平均值，用前缀和表示的话就是 ave(i,j)=Sj−Si−1j−(i−1) ，如果将S函数绘在平面直角坐标系内，这就是过点Sj和点Si-1直线的斜率！于是问题转化为：平面上已知N+1 个点，Pi(i, Si)，0≤i≤N，求横向距离大于等于F的任意两点连线的最大斜率。构造下凸曲线，用双端队列维护就可以了。具体证明可以参见周源2004IOI国家集训队论文。应该可以在网上搜到吧，搜不到可以去我的资源下。。。
#include<cstdio> #include<cstring> int const N=100000+10; int n,f,s[N],q[N],h=0,t=1;//q中至少有两个点才做判断 float ans,temp=0; int main(){ // freopen("poj2018.in","r",stdin); scanf("%d%d",&n,&f); for(int i=1;i<=n;++i){ int x;scanf("%d",&x);s[i]=s[i-1]+x; } q[++h]=0;ans=(float)(s[f]-s[0])/f; for(int i=1;i+f<=n;++i){ while(h<t&&(s[i]-s[q[t]])*(q[t]-q[t-1])<=(s[q[t]]-s[q[t-1]])*(i-q[t])) --t; q[++t]=i; while(h<t&&(s[i+f]-s[q[h]])*(i+f-q[h+1])<(s[i+f]-s[q[h+1]])*(i+f-q[h])) ++h; temp=(float)(s[i+f]-s[q[h]])/(i+f-q[h]); if(ans<temp) ans=temp; } printf("%d",(int)(1000*ans)); return 0; }