MAX Average Problem
Time Limit: 3000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld Java class name: Main
Consider a simple sequence which only contains positive integers as a1, a2 ... an, and a number k. Define ave(i,j) as the average value of the sub sequence ai ... aj, i<=j. Let’s calculate max(ave(i,j)), 1<=i<=j-k+1<=n.
Input
There multiple test cases in the input, each test case contains two lines.
The first line has two integers, N and k (k<=M<=10^5).
The second line has N integers, a1, a2 ... an. All numbers are ranged in [1, 2000].
Output
For every test case, output one single line contains a real number, which is mentioned in the description, accurate to 0.01.
Sample Input
10 6
6 4 2 10 3 8 5 9 4 1
Sample Output
6.50
Source
Author
HK@Sphinx
解题：单调队列+斜率优化
#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long LL;
const int maxn = ;
int q[maxn],hd,tl,n,k;
LL sum[maxn];
bool check(LL a,LL b,LL c){
return (sum[c] - sum[b])*(b - a) <= (sum[b] - sum[a])*(c - b);
}
int main(){
while(~scanf("%d%d",&n,&k)){
for(int i = ; i <= n; ++i){
scanf("%I64d",sum + i);
sum[i] += sum[i-];
}
double ret = ;
hd = tl = ;
for(int i = k; i <= n; ++i){
while(hd + < tl && check(q[tl-],q[tl-],i - k)) --tl;
q[tl++] = i - k;
while(hd + < tl && check(q[hd+],q[hd],i)) ++hd;
ret = max(ret,(sum[i] - sum[q[hd]])*1.0/(i - q[hd]));
}
printf("%.2f\n",ret);
}
return ;
}