HDU4268 Alice and Bob

　　原题传送：http://acm.hdu.edu.cn/showproblem.php?pid=4268

　　贪心算法。

　　对a、b数组进行二维排序（先按长h从小到大排序，相同的h按宽w从小到大排序），对于b的h小于a的h，把b的w添加到集合中，并从集合里面选择一个可以覆盖的最大的w即可（因为此时由于第一维h已经满足覆盖条件，只需要考虑第二维的w）。

　　这道题在比赛的时候没做出来，后来看了解题报告，才发现STL神器之multiset，这就是比赛时苦苦寻找的数据结构啊！这东西自己从来没用过的，此刻必须记录下它的两个重要特点：

　　1.它有优先队列的性质，插入的元素是有序的，插入复杂度和priority_queue一样只有O(log(n))；

　　2.它有两个很好用的方法：

　　　　a.lower_bound(key)：返回指向第一个">=key"的元素的迭代指针；

　　　　b.upper_bound(key)：返回指向第一个">key"的元素的迭代指针；

　　（这两个方法都是O(log(n))复杂度，很高效），并且删除操作也很容易。

View Code

 1 #include <stdio.h>
 2 #include <set>
 3 #include <algorithm>
 4 #define N 100001
 5 using namespace std;
 6 
 7 struct node
 8 {
 9     int h, w;
10 }a[N], b[N];
11 
12 multiset<int> s;
13 
14 bool cmp(node x, node y)
15 {
16     if(x.h < y.h)
17         return true;
18     else if(x.h == y.h)
19         return x.w < y.w ? true : false;
20     else 
21         return false;
22 }
23 
24 int main()
25 {
26     int n, i, j, cas, cnt;
27     scanf("%d", &cas);
28     while(cas --)
29     {
30         s.clear();
31         scanf("%d", &n);
32         for(i = 0; i < n; i ++)
33             scanf("%d%d", &a[i].h, &a[i].w);
34         for(i = 0; i < n; i ++)
35             scanf("%d%d", &b[i].h, &b[i].w);
36         sort(a, a + n, cmp);
37         sort(b, b + n, cmp);
38         for(cnt = i = j = 0; i < n; i++)
39         {
40             while(j < n && b[j].h <= a[i].h)
41             {
42                 s.insert(b[j].w);
43                 j ++;
44             }
45             if(!s.empty() && *s.begin() <= a[i].w)
46             {
47                 multiset <int>::iterator it = s.upper_bound(a[i].w);
48                 cnt ++;
49                 it --;
50                 s.erase(it);
51             }
52         }
53         printf("%d\n", cnt);
54     }
55     return 0;
56 }