自动搬运

查看原文

来自洛谷，原作者为

	Ccliang **

搬运于2025-08-24 22:18:10，当前版本为作者最后更新于2020-04-25 21:59:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我看到这个题目是真的没思路，然后看题解还只有一个而且没几行讲思路，快哭了$QAQ$。

为了避免别人也有我这种糟糕的体验，这篇题解诞生了。

先看题目，最大值最小，学过OI的都知道这要用到二分，直接二分枚举答案再$check$就好了。

再看$check$要怎么写。

设我们枚举的答案是$ans$，则我们分出来的每个区域的奶牛都要小于$ans$显而易见。

我们枚举 $y$ ，用两个树状数组维护 $y$ 上面区域和下面的奶牛数，然后求一个最优的 $x$。

但是如果直接枚举$x$，时间复杂度会直接到$n^2$，很明显不能直接枚举。

再仔细想想，假设我们是从小到大枚举$y$，那么上面区域的奶牛数会越来越少，下面的奶牛的数量会越来越多，所以对于上面区域，我们从小到大枚举$x$，设左上区域奶牛数刚好$<=ans$时$x=t1$，对于下面区域，我们从大到小枚举$x$，设左下区域奶牛数刚好$<=ans$时$x=t2$，则最优的$x$就是$min(t1,t2)$

$x$和$y$都确定了，再计算出其他两个区域的奶牛数就可以了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;

inline int read()
{
	int res=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
	return res;
}

struct Cow{
	int x,y;
	bool operator <(const Cow a) const{
        return y<a.y;
    }
}c[N];

int n,sb[N],xb[N];
#define lowbit(x) (x)&(-x)
void change(int a[],int x,int k)
{
	while(x<=n)
		a[x]+=k,x+=lowbit(x);
}

int query(int a[],int x)
{
	int res=0;
	while(x>0)
		res+=a[x],x-=lowbit(x);
	return res;
}

bool check(int x)
{
	memset(sb,0,sizeof(sb));
	memset(xb,0,sizeof(xb));
	for(int i=1;i<=n;i++)
		change(sb,c[i].x,1);
	int st=n,xt=0,zs=1,zx=n;
	for(int t,i=1,j=1;i<=n;i=j)
	{
		while(c[i].y==c[j].y)
			change(sb,c[j].x,-1),change(xb,c[j].x,1),st--,xt++,j++;
		while(zs<=n&&query(sb,zs)<=x)
			zs++;
		zs--;
		while(zx>0&&query(xb,zx)>x)
			zx--;
		t=min(zx,zs);
		if(xt-query(xb,t)<=x&&st-query(sb,t)<=x)
			return true;
	}
	return false;
}

pair<int,int>p[N];

int tot,mid,l,r,ans;

int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		c[i].x=read(),c[i].y=read(),p[i].first=c[i].x,p[i].second=i;
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++)
	{
		if(p[i].first!=p[i-1].first)
			tot++;
		c[p[i].second].x=tot;
	}
	sort(c+1,c+n+1);
	l=1,r=n;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid))
			r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%d\n",ans);
    return 0;
}