社区讨论

二维前缀和70分求助

P3138[USACO16FEB] Load Balancing S参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo8k8udx
此快照首次捕获于
2023/10/27 19:59
2 年前
此快照最后确认于
2023/10/27 19:59
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x[1005],tx[1005],y[1005],ty[1005],sum[1005][1005],ans=0x7fffffff;
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&x[i],&y[i]),tx[i]=x[i],ty[i]=y[i];
	sort(tx+1,tx+n+1);
	int len1=unique(tx+1,tx+n+1)-tx-1;
	for(int i=1;i<=n;i++) x[i]=lower_bound(tx+1,tx+len1+1,x[i])-tx;
	sort(ty+1,ty+n+1); 
	int len2=unique(ty+1,ty+n+1)-ty-1;
	for(int i=1;i<=n;i++) y[i]=lower_bound(ty+1,ty+len1+1,y[i])-ty;
	for(int i=1;i<=n;i++) sum[x[i]][y[i]]++;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			sum[i][j]=sum[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
	for(int i=2;i<=n;i+=2)
		for(int j=2;j<=n;j+=2)
		{
			int A,B,C,D;
			A=sum[i-1][j-1],B=sum[i-1][n]-sum[i-1][j],
			C=sum[n][j-1]-sum[i][j-1],D=sum[n][n]-sum[n][j]-sum[i][n]+sum[i][j];
			ans=min(max(max(A,B),max(C,D)),ans);
		}
	printf("%lld",ans);
}

回复

1 条回复,欢迎继续交流。

正在加载回复...