50RE 求调
  • 板块P1419 寻找段落
  • 楼主ruoyu_
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/26 09:48
  • 上次更新2024/10/26 12:14:59
查看原帖
50RE 求调
543779
ruoyu_楼主2024/10/26 09:48
#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define M 1005
#define INF 0x3f3f3f3f
int n,S,T,Q[N],A[N];
double B[N],eps=1e-5,sum[N];
bool check(double mid){
	for(int i=1;i<=n;i++)B[i]=(double)A[i]-mid;
	printf("%lf\n",sum[0]);
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+B[i];
	int l=1,r=0;
	Q[++r]=sum[1];
	for(int i=S;i<=n;i++){
		while(l<=r&&Q[l]+T<i)l++;
		while(l<=r&&sum[i-S]<=sum[Q[r]])r--;
		Q[++r]=i-S;
		if(sum[i]-sum[Q[l]]>=0)return 1;
	}
	return 0;
}
int main(){
	scanf("%d%d%d",&n,&S,&T);
	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
	double L=-1e4,R=1e4;
	while(L+eps<R){
		double mid=(L+R)/2;
		if(check(mid))L=mid;
		else R=mid; 
	}
	printf("%.3lf",L);
	return 0;
}
2024/10/26 09:48
加载中...