Alice and Bob hdu 4268

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

题意：

Alice 和 Bob 都有n张牌，分别有长和宽

存在一种覆盖操作：a牌可以覆盖b牌的条件为，b的长和宽必须均小于a

覆盖操作中不允许牌进行旋转。

问Alice手中的牌最多可以覆盖Bob手中多少张牌？注：覆盖成功的两张牌均被弃置。

思路：

首先肯定要把两人手中的牌按先长后宽从小到大排个序。

第一次尝试（超时）

刚开始的时候用multiset分别存了两个人的牌，然后从Alice开始遍历找Bob的牌，如果A牌的长宽均小于B牌时A立即换牌，不再遍历B牌（一定要遍历B的，不能只判断第一张牌，如果当前A为（4,5），B为（3,8），不能覆盖，但是B的下一张可能为（4,4），还是可以覆盖的，所以必须遍历）。

但是，即使加了这样简单的剪枝，还是 TLE。

第二次尝试（超内存）

经过第一次，发现怎么都要遍历两次，后来找到了一种方法，第一次遍历O(n)，第二次用二分去找O(logN)，这就快多了。

从Alice开始遍历，把B中所有长度小于等于当前A牌的Bob的牌均置于multiset中，然后找一个长度不大于当前A的牌，然后删掉，计一次数，用二分查找upper_bound。

时间是变成O(N log N)了，但是这个时候内存又超了，（？？），难道multiset还超内存，后来把Alice和Bob的存储改成了vector，心想这下总不会超内存了吧，但结果还是超内存。

第三次

实属无奈，只好把Alice和Bob的存储全都换成数组，然后就过了。。。。。。

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<set>
 4 #include<algorithm>
 5 using namespace std;
 6 class Card
 7 {
 8 public:
 9     int _h, _w;
10     bool operator<(const Card& rhs)const
11     {
12         return _h < rhs._h;
13     }
14 };
15 Card A[100001], B[100001];
16 multiset<int>C;
17 
18 int main()
19 {
20     int group, cardnum;
21     scanf("%d", &group);
22     while (group--)
23     {
24         C.clear();
25         scanf("%d", &cardnum);
26         int result = 0;
27         for (int i = 0; i < cardnum; ++i)
28             scanf("%d%d", &A[i]._h, &A[i]._w);
29         for (int i = 0; i < cardnum; ++i)
30             scanf("%d%d", &B[i]._h, &B[i]._w);
31         sort(A, A + cardnum);
32         sort(B, B + cardnum);
33         for (int i = 0, j = 0; i < cardnum; ++i)
34         {
35             while (j < cardnum && A[i]._h >= B[j]._h)
36             {
37                 C.insert(B[j]._w);
38                 ++j;
39             }
40             if (!C.empty() && A[i]._w >= *C.begin())
41             {
42                 multiset<int>::iterator t = C.upper_bound(A[i]._w);
43                 t--;
44                 result++;
45                 C.erase(t);
46             }
47         }
48         printf("%d
", result);
49     }
50 }

感谢您的阅读，生活愉快~