求助
  • 板块P1404 平均数
  • 楼主Edison688
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/3/28 09:10
  • 上次更新2023/11/5 01:28:06
查看原帖
求助
374109
Edison688楼主2021/3/28 09:10
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n,L,A[MAXN];

double ave(int li,int ri){
	double sum=double(A[ri]-A[li-1]);
	double n=double(ri-li+1);
	return sum/n;
}

double solve(int l,int r){
	int len=r-l+1;
	if(len<L)return 0.;
	if(len==L)return ave(l,r);
	int ml=l+(len-L+1)/2,mr=ml+L-1;
	double temp=0.;
	int maxl1=ml,maxl2=ml;
	for(int i=ml-1;i>=l;i--){
		if(temp<ave(i,ml-1)){
			temp=ave(i,ml-1);
			maxl1=i;
		}
		if(temp==ave(i,ml-1)){
			maxl2=i;
		}
	}
	temp=0.;
	int maxr1=mr,maxr2=mr;
	for(int i=mr+1;i<=r;i++){
		if(temp<ave(mr+1,i)||(temp==ave(i,mr+1)&&temp>ave(ml,mr))){
			temp=ave(mr+1,i);
			maxr1=i;
		}
		if(temp==ave(mr+1,i)){
			maxr2=i;
		}
	}
	temp=ave(ml,mr);
	temp=max(temp,ave(ml,maxr1));
	temp=max(temp,ave(ml,maxr2));
	temp=max(temp,ave(maxl1,mr));
	temp=max(temp,ave(maxl1,maxr1));
	temp=max(temp,ave(maxl1,maxr2));
	temp=max(temp,ave(maxl2,mr));
	temp=max(temp,ave(maxl2,maxr1));
	temp=max(temp,ave(maxl2,maxr2));
	temp=max(temp,solve(l,mr-1));
	temp=max(temp,solve(ml+1,r));
	return temp;
}

int main(){
	cin>>n>>L;
	if(L==0){cout<<"0";return 0;}
	int t;
	for(int i=1;i<=n;i++){
		cin>>t;
		A[i]=A[i-1]+t;
	}
	int res=int(solve(1,n)*1e3);
	cout<<res<<endl;
	return 0;
}
2021/3/28 09:10
加载中...