自动搬运

查看原文

来自洛谷，原作者为

	曹老师 **

搬运于2025-08-24 21:45:42，当前版本为作者最后更新于2018-06-13 15:21:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感谢@mimi提供二维前缀和做法

知识点：二维前缀和

先离散化处理！

再预处理前缀和

输出四个象限中的最大值

max(max(sum[i][j],sum[i][n]-sum[i][j]),max(sum[n][j]-sum[i][j],sum[n][n]-sum[n][j]-sum[i][n]+sum[i][j]))

用一个超长的max来做

里面四个对比的值分别为四个象限内的数

自己理解一下，易懂

然后输出最小的最大值~~(如此绕嘴想到二分)~~就好了

时间复杂度：O(n^2)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#define MAXN 100005
#define LL long long
#define INF 2147483647
#define MOD 1000000007
#define free(s) freopen("s.txt","r",stdin);
#define lowbit(x) ((x&(-x))) 
#define debug(x) cout<<x<<endl;
using namespace std;
const int L=1005;
struct node{
	LL int s,num;
};
node zx[L],zy[L];
bool cmp(const node &b,const node &c)
{
	return b.s<c.s;
}
LL int n,x[L],y[L],ans=INF,sum[L][L];
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&zx[i].s,&zy[i].s);
		zx[i].num=i;
		zy[i].num=i;
	}
	sort(zx+1,zx+n+1,cmp);
	sort(zy+1,zy+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		x[zx[i].num]=i;
		y[zy[i].num]=i;
	}//离散化 
	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-1][j]+sum[i][j-1]-sum[i-1][j-1];//预处理部分 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			ans=min(ans,max(max(sum[i][j],sum[i][n]-sum[i][j]),max(sum[n][j]-sum[i][j],sum[n][n]-sum[n][j]-sum[i][n]+sum[i][j])));//四个象限 
	printf("%lld",ans);
	return 0;
}