社区讨论
二维前缀和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 条回复,欢迎继续交流。
正在加载回复...