详见,算法合集之《浅谈数形结合思想在信息学竞赛中的应用》。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; double sum[100010]; int q[100010]; bool judge(int i,int j,int k) { // if((sum[j]-sum[i])/(j-i)>=(sum[k]-sum[i])/(k-i)) if((sum[j]-sum[i])*(k-i)-(sum[k]-sum[i])*(j-i)>=0) return true; //存在上凸点 return false; } double f(int i,int j) { return (sum[j]-sum[i])/(j-i); } inline int ReadInt() { char ch = getchar(); int data = 0; while (ch < '0' || ch > '9') { ch = getchar(); } do { data = data*10 + ch-'0'; ch = getchar(); }while (ch >= '0' && ch <= '9'); return data; } int main() { int n,k; double ans; while(scanf("%d%d",&n,&k)!=EOF) { sum[0]=0; for(int i=1;i<=n;i++) sum[i]=sum[i-1]+ReadInt(); int head=0,tail=0; ans=0; for(int i=k;i<=n;i++) { while(head<tail && judge(q[tail-1],q[tail],i-k)) tail--; q[++tail]=i-k; while(head<tail && f(q[head+1],i)>=f(q[head],i)) head++; ans=max(ans,f(q[head],i)); } printf("%.2lf\n",ans); } return 0; }