自动搬运

查看原文

来自洛谷，原作者为

	Dream__Sky 欲买桂花同载酒，终不似，少年游。便邀东风揽明月，春不许，再回头

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

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

以下是正文

此题用暴力的解法，即枚举每一个是否能被其它牛圈覆盖，复杂度 $O(n^2)$ ，并不能通过。本题可以使用优化暴力的做法。

我这里用 $x_i,y_i,x1_i,y1_i$ 表示第 $i$ 个牛圈的上左下右。用 $x_j,y_j,x1_j,y1_j$ 表示第 $j$ 个牛圈的上左下右。

首先要注意，如何判断有没有被包含：

当牛圈 $j$ 包含 牛圈 $i$ 时，

$x_j < x_i$

$y_j < y_i$

$y1_j > y1_i$

$x1_j > x1_i$

接着，我们可以用类似单调队列的想法，将所有牛圈按照某一条边排序，使牛圈有序。例如，如果按照 $x_i$ 从小到大排序后，当前面的牛圈的最底下一条边，即 $x1_i < x_j$ 时，那么肯定是不可行的。也就是说，每一次我们不必从头开始查询，只要从上一次查询的地方起，去掉那些已经不可能被包含的牛圈，再开始判断能否被包含即可。

附代码：

#include<bits/stdc++.h>
using namespace std;
int n,b[50001],ans,l=1,r=2;
struct node
{
	int x,y,xx,yy;//分别是上左下右的坐标
}a[50001];
bool cmp(node x,node y)
{
	return x.x<y.x;
}//按照边排序
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y>>a[i].xx>>a[i].yy;
	sort(a+1,a+n+1,cmp);
	ans=n;
	while(r<=n)
	{
		while(a[l].xx<=a[r].x)l++;//将前面已不可能被包围的牛圈删去
		for(int i=l;i<=r;i++)
		  if(a[r].x>a[i].x&&a[r].yy<a[i].yy&&a[i].y<a[r].y&&a[i].xx>a[r].xx)
			{ 
				ans--;
				break;
			}//在可能的牛圈中，逐个比较，直到发现被包围
         		//如果发现，那么不被包围的牛圈个数就减一
		r++;
	}
	cout<<ans;//输出答案
   	return 0;
}