MAX Average Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5803 Accepted Submission(s): 1433
Problem Description
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.
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<=N<=10^5).
The second line has N integers, a1, a2 ... an. All numbers are ranged in [1, 2000].
The first line has two integers, N and k (k<=N<=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
6 4 2 10 3 8 5 9 4 1
Sample Output
6.50
这道题不是普通的斜率优化，详细题解参见：http://blog.sina.com.cn/s/blog_ad1f8960010174el.html
由于把题目数据范围从10^4提到了5*10^5，我用自己出的数据对拍，网上的标程基本爆掉。
只有一点要注意，就是不加读入优化绝对TLE。一般O(n)的题都是这样。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long double real;
#define MAXN 510000
#define max(x,y) ((x)>(y)?(x):(y))
typedef long long qword;
int num[MAXN];
int sum[MAXN];
int n;
real f[MAXN];
real ans=;
struct Point
{
qword x,y;
}pl[MAXN];
int topl=-;
qword xmul(Point p1,Point p2,Point p3)
{
return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
}
real get_k(Point p1,Point p2)
{
return real(p1.y-p2.y)/(p1.x-p2.x);
}
inline int getInt(int &ret)
{
char ch=getchar();
ret=;
while (ch>''||ch<'')ch=getchar();
while ()
{
ret=ret*+ch-'';
ch=getchar();
if (ch>''||ch<'')break;
}
} int main()
{
freopen("input.txt","r",stdin);
int i,j,k;
while (~scanf("%d%d",&n,&k))
{
Point pp;
for (i=;i<=n;i++)
{
// scanf("%d",&num[i]);
getInt(num[i]);
sum[i]=sum[i-]+num[i];
}
/*
for (i=1;i<=n;i++)
{
for (j=i-k+1;j>=1;j--)
{
ans=max(ans,real(sum[i]-sum[j-1])/(i-j+1));
}
}*/
ans=;
int ptr=-;
int now;
Point pi;
int head=;
topl=-;
for (i=;i<=n;i++)
{
now=i-k;
if (now<)continue;
pi.x=i;pi.y=sum[i];
pp.x=now;
pp.y=sum[now];
if (topl<=head)
{
pl[++topl]=pp;
}else
{
while (topl>=head+&&xmul(pl[topl-],pl[topl],pp)<=)
{
topl--;
}
pl[++topl]=pp;
}
while (ptr==-||(ptr<topl&&get_k(pl[ptr],pi)<=get_k(pl[ptr+],pi)))
{
ptr++;
head=ptr;
}
if (ans<get_k(pl[ptr],pi))
{
--++i;
}
ans=max(ans,get_k(pl[ptr],pi));
}
printf("%.2lf\n",(double)ans);
}
return ;
}