P3079题解

Dream__Sky · 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_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;
}