二分30分……
查看原帖
二分30分……
658786
STUDENT00楼主2022/10/7 22:17

请问二分的思路有问题吗?

代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,k,a[100010],sum[100010][30],ans,l,r;
bool mean(int *s){
	for(int i=1;i<k;i++){
		if(s[i]!=s[i-1]) return 0;
	}
	return 1;
}
bool check(int d){
	int s[30];
	for(int i=d;i<=n;i++){
		for(int j=0;j<k;j++) s[j]=sum[i][j]-sum[i-d][j];
		if(mean(s)) return 1;
	}
	return 0;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		for(int j=0;j<k;j++) sum[i][j]=sum[i-1][j]+((a[i]>>j)&1);
	}
	l=1;
	r=n;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			l=mid+1;
		}else r=mid-1;
	}
	printf("%d",ans);
	return 0;
}
2022/10/7 22:17
加载中...