二分+前缀和求助
查看原帖
二分+前缀和求助
520056
luoyx楼主2022/8/4 18:17

最后输出答案时每次都比答案大1,后来输出答案时-1就过了,求助大佬原因。

#include <bits/stdc++.h>
#define N 1005
using namespace std;
int f[N][N];
int n,m;
int x,y;
int a[N][N];
bool check(int mid){
	int ans=1;
	for(int i=1,ii=mid;ii<=n;i++,ii++){
		for(int j=1,jj=mid;jj<=n;j++,jj++){
			ans=min(ans,f[ii][jj]-f[i-1][jj]-f[ii][j-1]+f[i-1][j-1]);
		}
	}
	return ans==0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		a[x][y]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-1]+a[i][j];
		}
	}
	int l=1,r=n,mid;
	while(l<=r){
		mid=(r-l)/2+l;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
	cout<<l-1;
}
2022/8/4 18:17
加载中...