126pts dp求调
查看原帖
126pts dp求调
977901
int4399楼主2024/8/26 17:11
#define P node 
using namespace std;
struct node{
	long long sum,len;
	long double data;
};
const int N=3e5+5;
int n,k;
long long a[N],b[N];
P dp[N];
long double ans;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=b[i-1]+a[i];
	}
	for(int i=k;i<=n;i++){
		double last=(dp[i-1].sum+a[i])*1.0/(dp[i-1].len+1);
		double mee=(b[i]-b[i-k])*1.0/k;
		if(i==k||last<=mee){
			dp[i].data=mee;
			dp[i].len=k;
			dp[i].sum=b[i]-b[i-k];
		}else{
			dp[i].data=last;
			dp[i].len=dp[i-1].len+1;
			dp[i].sum=b[i]-b[i-dp[i].len];
		}
		ans=max(ans,dp[i].data);
	}
 	printf("%.6Lf",ans);
	return 0;
}```
2024/8/26 17:11
加载中...