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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<deque>
using namespace std;
const int SIZEN=100010;
class POINT{
public:
	double x,y;
};
void print(POINT p){cout<<"("<<p.x<<","<<p.y<<")";}
POINT operator - (POINT a,POINT b){return (POINT){a.x-b.x,a.y-b.y};}
double crp(POINT a,POINT b){return a.x*b.y-b.x*a.y;}
double calc_k(POINT a,POINT b){return (a.y-b.y)/(a.x-b.x);}
int N,K;
int S[SIZEN]={0};
deque<POINT> Q;
double ans;
//第i个点的坐标是(i,S[i])
void addpoint(POINT p){
	while(Q.size()>1&&crp(p-Q.back(),Q.back()-Q[Q.size()-2])>=0) Q.pop_back();
	Q.push_back(p);
}
void work(void){
	ans=-1e9;
	for(int i=1;i<=N;i++){
		if(i>=K){
			addpoint((POINT){i-K,S[i-K]});
			POINT now=(POINT){i,S[i]};
			while(Q.size()>1&&crp(Q[1]-Q[0],now-Q[0])>0) Q.pop_front();
			ans=max(ans,calc_k(Q[0],now));
		}
	}
	printf("%d\n",(int)(ans*1000));
}
void read(void){
	scanf("%d%d",&N,&K);
	S[0]=0;
	for(int i=1;i<=N;i++) scanf("%d",&S[i]),S[i]+=S[i-1];
}
int main(void){
	freopen("avanum.in","r",stdin);
	freopen("avanum.out","w",stdout);
	read();
	work();
	return 0;
}