HDU4268 Alice and Bob（贪心+multiset）

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<string>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<set>
 8 
 9 using namespace std;
10 
11 struct card
12 {
13     int h,w;    
14 };
15 
16 int cmp(card a,card b)
17 {
18     if(a.h==b.h)
19     {
20         return a.w<b.w;
21     }
22     return a.h<b.h;
23 }
24 
25 int main()
26 {
27     int k,m,q,t,p,n;
28     int T;
29     cin>>T;
30     while(T--)
31     {
32         int ans=0;
33         card a[100000],b[100000];
34         multiset<int> ms;
35         multiset<int>::iterator it;
36         
37         cin>>n;
38         for(int i=0;i<n;++i)
39         {
40             scanf("%d %d",&a[i].h,&a[i].w);
41         }
42         for(int i=0;i<n;++i)
43         {
44             scanf("%d %d",&b[i].h,&b[i].w);
45         }
46         
47         sort(a,a+n,cmp);
48         sort(b,b+n,cmp);
49         
50          int i=0,j=0;
51          for(;i<n;++i)
52          {
53             while(j<n&&(a[i].h>=b[j].h))
54             {
55                 ms.insert(b[j].w);
56                 ++j;
57             }
58             if(ms.empty())
59             {
60                 continue;
61             }
62             
63             it=ms.upper_bound(a[i].w);
64             if(it==ms.begin())
65             {
66                 continue;
67             }else
68             {
69                 --it;
70                 ++ans;
71                 ms.erase(it);
72             }
73             
74          }
75          cout<<ans<<endl;
76          
77     }
78     return 0;
79 }