60分求助
查看原帖
60分求助
933414
User_10_noob楼主2024/9/16 14:24

蒟蒻用的二分答案,WA了4,7,8,11,可能是check函数有什么漏洞

#include<bits/stdc++.h>
using namespace std;
inline void read(int &n){
	n=0;char c;
	c=getchar();
	while (c>'9'||c<'0') c=getchar();
	while (c<='9'&&c>='0'){
		n=(n<<1)+(n<<3)+(c^48);
		c=getchar();
	}
}
const int N=1e5+5;
int s[N],b[N],n;
bool check(int x){//x为区间长度,保证x必须为偶数 
	if (s[n]*2<x||x&1) return 0;
	for (int i=b[x/2];i<=n;i++){
		if (i>x||i==n){//保证下标不越界
			if ((s[i]-s[i-x])*2==x) return 1;
		}
	}
	return 0;
}
int main(){
	read(n);
	for (int i=1;i<=n;i++){
		read(s[i]);s[i]+=s[i-1];
		if (!b[s[i]]) b[s[i]]=i;
	}
	int l=0,r=n/2+1;//对区间长度的一半进行二分答案 
	while (l<=r){
		int mid=l+r>>1;
		if (check(mid*2)) l=mid+1;
		else r=mid-1;
	}
	cout<<r*2; 
	return 0;
}
2024/9/16 14:24
加载中...