具體分析間NOI論文：
淺談數形結合思想在信息學競賽中的應用，例題2
直接貼代碼了。。
再次注意消除浮點誤差時中間運算結果超出int范圍！！
1 # include <stdio.h>
2 # define N 100005
3 # define less(x1,y1,x2,y2,x3,y3,x4,y4) (y2-y1)*(x4-x3)<=(y4-y3)*(x2-x1)
4 # define max(a,b) ((a)>(b)?(a):(b))
5 int data[N],q[N][2],s=-1,e=-1;
6 int n,f;
7 int main()
8 {
9 int i;
10 scanf("%d%d",&n,&f);
11 data[0]=0;
12 for(i=1;i<=n;i++)
13 {
14 scanf("%d",data+i);
15 data[i]+=data[i-1];
16 }
17 e++;
18 q[e][0]=0;
19 q[e][1]=0;
20 double res;
21 int y=-1,x=-1;
22 for(i=1;i<=n;i++)
23 {
24 while(s+2<=e&&i-q[s+2][0]>=f) s++;
25 while(e>=s+2&&less(q[e][0],q[e][1],i,data[i],q[e-1][0],q[e-1][1],q[e][0],q[e][1])) e--;
26 e++;
27 q[e][0]=i;
28 q[e][1]=data[i];
29 if(s<e&&i-q[s+1][0]>=f)
30 if(y==-1&&x==-1||x!=-1&&y!=-1&&((long long)data[i]-q[s+1][1])*x>(long long)y*(i-q[s+1][0]))
31 y=data[i]-q[s+1][1],x=i-q[s+1][0];
32 }
33 printf("%d\n",(long long)(y*1000)/x);
34 return 0;
35 }