题意：

有童鞋A 和 童鞋B

A想用手里的牌尽量多地覆盖掉B手中的牌..

给出了T表示有T组样例..

每组样例给出一个n 表示A和B手中都有n张牌

接下来2*n行 有h w 分别代表A手中n张牌的高和宽 以及 B手中n张牌的高和宽

问A手中的牌最多能覆盖B多少张牌

思路：

对一个坐标排序

假设是x坐标

然后扫描

维护一个y坐标

然后每次取的是堆里面最大的

Tips：

set里的一个函数..在短时间内找到 b的w 中满足小于a的w的值~

iterator lower_bound( const key_type &key ): 返回一个，指向键值>= key的第一个元素。

iterator upper_bound( const key_type &key ):返回一个迭代器，指向

键值

> key

的第一个元素。

 

※ 因为找到的是 >= key的第一个元素..所以为了删除 比当前牌小的..应该it--

Code：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7 #define clr(x) memset(x, 0, sizeof(x)) 8  9 struct Card10 {11     int w;12     int h;13 }a[100010], b[100010];14 15 int cmp(Card a, Card b)16 {17     if(a.h != b.h) return a.h < b.h;18     else return a.w < b.w;19 }20 21 int main()22 {23     int i, j, k;24     int p, q;25     int T, n;26     int sum;27     while(scanf("%d", &T) != EOF)28     while(T--)29     {30         sum = 0;31         multiset
           
             s;32 33 scanf("%d", &n);34 for(i = 0; i < n; ++i)35 scanf("%d %d", &a[i].h, &a[i].w);36 for(i = 0; i < n; ++i)37 scanf("%d %d", &b[i].h, &b[i].w);38 39 sort(a, a+n, cmp);40 sort(b, b+n, cmp);41 42 for(i = 0, j = 0; i < n; ++i){43 while(j < n && b[j].h <= a[i].h){44 s.insert(b[j].w);45 j++;46 }47 if(s.size() == 0) continue;48 set
            
             ::iterator it = s.upper_bound(a[i].w);49 if(it != s.begin()){50 sum++;51 it--;52 s.erase(it);53 }54 }55 printf("%d\n", sum);56 }57 return 0;58 }