关于二分部分的疑惑
查看原帖
关于二分部分的疑惑
800726
hzx202303楼主2025/7/22 14:37

为什么将这份代码的二分部分改为下一份代码的二分部分能过,有大佬能解释一下吗?

第一份

#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef complex<double> cp;//fushu
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
const int N=1e6+10;
const ll inf=1e18+10;
const ll mod=1e9+7;
using Vl=vector<ll>;
ll n,L;
double l=0,r=2000,s[N],a[N],ans;
bool ck(double mid){
	for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-mid;
	double mn=0;
	for(int i=L;i<=n;i++){
		mn=min(mn,s[i-L]);
		if(s[i]-mn>=0) return 1;
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	mt19937 myrand(time(0));
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>L;
	for(int i=1;i<=n;i++) cin>>a[i];
	while(r-l>1e-5){
		double mid=(l+r)*0.5;
		if(ck(mid)) l=mid+1,ans=mid;
		else r=mid-1;
	}
	cout<<(ll)(ans*1000)<<'\n';
	return 0;
}

第二份

#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef complex<double> cp;//fushu
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
const int N=1e6+10;
const ll inf=1e18+10;
const ll mod=1e9+7;
using Vl=vector<ll>;
ll n,L;
double l=0,r=2000,s[N],a[N],ans;
bool ck(double mid){
	for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-mid;
	double mn=0;
	for(int i=L;i<=n;i++){
		mn=min(mn,s[i-L]);
		if(s[i]-mn>=0) return 1;
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	mt19937 myrand(time(0));
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>L;
	for(int i=1;i<=n;i++) cin>>a[i];
	while(r-l>1e-5){
		double mid=(l+r)*0.5;
		if(ck(mid)) l=mid;
		else r=mid;
	}
	cout<<(ll)(r*1000)<<'\n';
	return 0;
}
2025/7/22 14:37
加载中...