75pts二分求调,有注释,玄关
查看原帖
75pts二分求调,有注释,玄关
967959
TH911楼主2024/8/30 13:56

RT\text{RT},二分枚举区间长度,代码如下:

//#include<bits/stdc++.h>//个人习惯,忽略
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
const ll N=3e5;
ll n,a,b,c,s[N+1];
bool check(ll len){//检查长度为len行不行
	for(ll l=1,r=len;r<=n;l++,r++){
		if(s[r]-s[l-1]>=a*(b*r-c*l))return true;
	}return false;
}
int main(){ 
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/
	
	scanf("%lld %lld %lld %lld",&n,&a,&b,&c);
	for(ll i=1;i<=n;i++){
		scanf("%lld",s+i); 
		s[i]+=s[i-1];//前缀和维护
	}
	ll l=1,r=n,mid,ans;
	while(l<=r){//二分枚举长度
		mid=(l+r)/2;
		if(check(mid))l=mid+1,ans=mid;
		else r=mid-1;
	}printf("%lld\n",ans);//输出
	
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}
2024/8/30 13:56
加载中...