记录编号	377746	评测结果	AAAAAAAAAA
题目名称	1701.[USACO Mar03]最大平均值	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.085 s
提交时间	2017-03-02 01:35:50	内存使用	1.45 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define MAXN 100002
int a[MAXN], sum[MAXN];
int q[MAXN];
double getk(int l, int r){
  return (sum[r]-sum[l-1])*1.0/(r-l+1);
}                                                                              
int main(){
  freopen("avanum.in", "r", stdin);
  freopen("avanum.out", "w", stdout);
  int n, k; scanf("%d %d", &n, &k);
  sum[0] = 0;
  for(int i = 1; i <= n; i++){
    scanf("%d", a+i); sum[i] = sum[i-1]+a[i];
  }
  double res = -1e15;
  deque<int> q;
  for(int i = k; i <= n; i++){
    while(!q.empty() && q.front() > i-k)q.pop_front();
    while(!q.empty() && getk(q.back(), i) < getk(i-k+1, i))q.pop_back();
    q.push_back(i-k+1);
    res = max(res, getk(q.front(), i));
  }
  printf("%d\n", int(res*1000));
  return 0;
}