hdu 4268 multiset+贪心

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

 1 /*
 2 HDU 4268
 3 贪心+STL
 4 */
 5 
 6 #include<stdio.h>
 7 #include<math.h>
 8 #include<iostream>
 9 #include<set>
10 #include<algorithm>
11 using namespace std;
12 const int MAXN=200010;
13 struct Node
14 {
15     int h,w;
16     int flag;
17 }node[MAXN];
18 bool cmp(Node a,Node b)
19 {
20     if(a.h!=b.h)return a.h<b.h;
21     else if(a.w!=b.w)return a.w<b.w;
22     else return a.flag>b.flag;
23 }
24 multiset<int>mt;
25 multiset<int>::iterator it;
26 int main()
27 {
28     #ifndef ONLINE_JUDGE
29     freopen("1.in","r",stdin);
30     #endif
31     int T;
32     int n;
33     scanf("%d",&T);
34     while(T--)
35     {
36         scanf("%d",&n);
37         for(int i=1;i<=n;i++)
38         {
39             scanf("%d%d",&node[i].h,&node[i].w);
40             node[i].flag=1;
41         }
42         for(int i=n+1;i<=2*n;i++)
43         {
44             scanf("%d%d",&node[i].h,&node[i].w);
45             node[i].flag=2;
46         }
47         sort(node+1,node+2*n+1,cmp);
48         mt.clear();
49         /*for(int i=1;i<=2*n;i++)
50         {
51             printf("%d %d %d
",node[i].h,node[i].w,node[i].flag);
52         }*/
53         int ans=0;
54         for(int i=1;i<=2*n;i++) //1覆盖2
55         {
56             if(node[i].flag==2)mt.insert(node[i].w);
57             else
58             {
59                 if(!mt.empty())
60                 {
61                     it=mt.begin();
62                     if(node[i].w>=(*it))    //multiset是升序排列的，每次begin是出来最小的值，这个值不一定最接近w，所以需要重新找
63                     {
64                         ans++;
65                         it=mt.upper_bound(node[i].w);
66                         it--;
67                         mt.erase(it);
68                     }
69                 }
70             }
71         }
72         printf("%d
",ans);
73     }
74     return 0;
75 }