hdu4268 Alice and Bob

题目大意：

Alice和Bob有n个长方形，有长度和宽度，一个矩形可以覆盖另一个矩形的条件的是，本身长度大于等于另一个矩形，且宽度大于等于另一个矩形，矩形不可旋转，问你Alice最多能覆盖Bob的几个矩形？

 (N <= 100,000)

题解：

先按照x排序，先保证在x满足条件的情况下，对b[i].y(Bob)进行查找，找到最接近a[i].y(Alice)的值，删除他。

总之就是先保证一维有序这样可以O（n）枚举，另一维再查找。

#include<iostream>
#include<set>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
multiset<int> myset;
multiset<int>::iterator it;
const int maxn=200000;
struct node
{
    int x,y;
    bool operator<(const node& b)const
    {
        return x<b.x;
    }
}a[maxn],b[maxn];
int main()
{
    int sec,n;
    scanf("%d",&sec);
    for(int z=1;z<=sec;z++)
    {
        myset.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
        for(int i=1;i<=n;i++)
        scanf("%d%d",&b[i].x,&b[i].y);
        sort(a+1,a+1+n);//按x从小到大排序
        sort(b+1,b+1+n);//按x从小到大排序
        int j=1;int ans=0;//j是一个指向B数组位置的指针
        for(int i=1;i<=n;i++)
        {
            while(j<=n&&b[j].x<=a[i].x)
            {
                myset.insert(b[j].y);
                j++;
            }
            it=myset.upper_bound(a[i].y);
            if(myset.size()>0&&it!=myset.begin())it--;
            if(myset.size()>0&&(*it)<=a[i].y)
            {
                ans++;
                myset.erase(it);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}