HDU 4268 Alice and Bob [贪心]

　　贪心，用set水过。

　　先按x，后按y排序，都想等时Bob放前面。然后扫一遍遇到Bob就将卡片的y值放入set中，遇到Alice就在集合中找一个能被他覆盖的y最大的数，将它擦去。因为如若能覆盖而不去覆盖了就等于浪费了这个，所以必然选择用掉这张卡片。最后统计一共成功覆盖了多少个即可。

 1 #include <string.h>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <set>
 5 #define inset multiset<int,greater<int> >
 6 using namespace std;
 7 struct mat{
 8     int x,y,t;
 9     bool operator <(const mat& m)const
10     {return x<m.x||(x==m.x&&y<m.y)||(x==m.x&&y==m.y&&t<m.t);}
11 }m[200005];
12 inset st;
13 inset::iterator sit;
14 int cas,n,ans;
15 int main(){
16     for(scanf("%d",&cas);cas--;){
17         scanf("%d",&n);
18         for(int i=0;i<2*n;i++)
19             scanf("%d%d",&m[i].x,&m[i].y),
20             m[i].t=(i<n?1:0);
21         sort(m,m+2*n);
22         st.clear();ans=0;
23         for(int i=0;i<2*n;i++){
24             if(m[i].t==0)
25                 st.insert(m[i].y);
26             else if((sit=st.lower_bound(m[i].y))!=st.end())
27                 st.erase(sit),ans++;
28         }
29         printf("%d\n",ans);
30     }
31     return 0;
32 }