记录编号	118949	评测结果	AAAAAAAAAA
题目名称	[USACO Mar03]最大平均值	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.156 s
提交时间	2014-09-10 09:31:03	内存使用	0.75 MiB

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<string.h>

using namespace std;
const int MAXN=1e5+10;
const double INF=1e8;

int N,K;

int num[MAXN],sum[MAXN];

void init(){
	memset(num,0,sizeof(num));
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=N;i++)scanf("%d",&num[i]),sum[i]=num[i]+sum[i-1];
}

double cal_k(int x1,int x2){
	return double(sum[x2]-sum[x1])/double(x2-x1);
}
void work(){
	deque<int> q;
	double ans=-INF;
	for(int i=K-1;i<=N;i++){
		int x3=i;
		double tmp=-INF;
		bool first=true;
		while(!q.empty()){
			int tx;
			if(!first && q.size()<2)break;
			if(!first)tx=q.front(),q.pop_front();
			int x1=q.front();
			double tt=cal_k(x1,x3);
			if(tt>tmp){
				tmp=tt;
			}else if(!first){
				q.push_front(tx);
				break;
			}
			first=false;
		}
		if(q.size()==1){
			int tx=q.front();
			tmp=max(tmp,cal_k(tx,x3));
		}
		ans=max(ans,tmp);
		
		bool ok=false;
		x3=i-(K-1);
		while(q.size()>=2){
			int x1,x2;
			x2=q.back();q.pop_back();
			x1=q.back();
			
			double k1=cal_k(x1,x2);
			double k2=cal_k(x2,x3);
			if(k2>k1){
				q.push_back(x2);
				q.push_back(x3);
				ok=true;
				break;
			}
		}
		if(!ok)q.push_back(x3);
	}
	printf("%d\n",int(ans*1000));
}

int main(){
	freopen("avanum.in","r",stdin);
	freopen("avanum.out","w",stdout);
	while(scanf("%d %d",&N,&K)==2){
		init();
		work();
	}
	return 0;
}