题解

论文题2333,某中学大佬写的论文,建议搞懂思路没必要去AC,卡IO,快速读入输出都会T…
题意是求 $max(\frac{a[i]+a[i+1]+...+a[j]}{j-i+1}) (j-i>k)$
分子显然可以用前缀和优化,转换为求 $max(\frac{sum[i]-sum[j]}{j-i}) (j-i>k)$

这其实就是在N+1个点(i,sum[i])中求横坐标距离大于k的点对斜率的最值.显然是斜率dp


#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e5+7;
const int BUF = 25000000;
int q[N],sum[N],n,k;
char Buf[BUF],*buf=Buf;
template <typename T>inline void read(T &x){
	for(x=0;*buf<'0';buf++);
	while(*buf>='0')x=x*10+*buf++-'0';
}
inline int useless2(int a,int b,int c){return (1LL*sum[c]-sum[b])*(b-a)<=(1LL*sum[b]-sum[a])*(c-b);}
inline int useless1(int a,int b,int c){return (1LL*sum[c]-sum[b])*(c-a)<=(1LL*sum[c]-sum[a])*(c-b);}
int main(){
	int tot=fread(Buf,1,BUF,stdin);
	while(1){
		if(buf-Buf+1>=tot)break;
		read(n);read(k);
		rep(i,1,n){
			read(sum[i]);
			sum[i]+=sum[i-1];
		}
		int head=1,tail=0;double ans=-0x3f3f3f3f;
		rep(i,k,n){
			while(head<tail&&useless2(q[tail-1],q[tail],i-k))tail--;
			q[++tail]=i-k;
			while(head<tail&&useless1(q[head+1],q[head],i))head++;
			ans=max(1.0*(sum[i]-sum[q[head]])/(i-q[head]),ans);
		}
		printf("%.2lf\n",ans);
	}
}