精度二分取L和R的问题
查看原帖
精度二分取L和R的问题
616733
Lysea楼主2024/6/18 10:32

为什么取L有WA,换成R就A了啊,这玩意儿理应没啥区别吧。

#include<bits/stdc++.h>
#define int long long
#define N 5000005
#define INF 1e18
using namespace std;
double eps=1e-7,l,r,mid,ans,c[N],minn;
int n,m,b,a[N];
bool check(double x){
	for(int i=1;i<=n;i++) c[i]=a[i]-x,c[i]+=c[i-1];
	minn=INF,ans=-INF;
	for(int i=m;i<=n;i++){
		minn=min(minn,c[i-m]);
		ans=max(ans,c[i]-minn);
	}
	return ans>=0;
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i],a[i]*=1000;
	l=-1e9,r=1e9;
	while(r-l>eps){
		mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	cout<<(int)r;
//	cout<<(int)l;
    return 0;
}

2024/6/18 10:32
加载中...