求助大佬,悬关
查看原帖
求助大佬,悬关
752711
hateful_bug楼主2024/7/9 17:01

为什么这种离散化方式只有90pt

#include<bits/stdc++.h>
using namespace std;
int n,mx,my,x[1005],y[1005],x2[1005],y2[1005],qzh[1005][1005],ans=1000000;//qzh是前缀和
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d%d",&x[i],&y[i]),x2[i]=x[i],y2[i]=y[i];
	sort(x2+1,x2+n+1);
	sort(y2+1,y2+n+1);
	mx=unique(x2+1,x2+n+1)-x2;
	my=unique(y2+1,y2+n+1)-y2;
	for(int i=1;i<=n;i++)
	x[i]=lower_bound(x2+1,x2+mx+1,x[i])-x2,y[i]=lower_bound(y2+1,y2+my+1,y[i])-y2;
	for(int i=1;i<=n;i++)
	++qzh[x[i]][y[i]];
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	qzh[i][j]+=qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1];
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	ans=min(ans,max(max(qzh[i][j],qzh[i][n]-qzh[i][j]),max(qzh[n][j]-qzh[i][j],qzh[n][n]-qzh[n][j]-qzh[i][n]+qzh[i][j])));
	printf("%d",ans);
	return 0;
}
2024/7/9 17:01
加载中...