Alice and Bob
time limit per test 5 second memory limit per test 256 megabytes
Alice and Bob’s game never ends. Today, they introduce a new game. In this game, both of them have N different rectangular cards respectively. Alice wants to use his cards to cover Bob’s. The card A can cover the card B if the height of A is not smaller than B and the width of A is not smaller than B. As the best programmer, you are asked to compute the maximal number of Bob’s cards that Alice can cover.
Please pay attention that each card can be used only once and the cards cannot be rotated.

传送门:HDU4268

Input

The first line of the input is a number T (T <= 40) which means the number of test cases. For each case, the first line is a number N which means the number of cards that Alice and Bob have respectively. Each of the following N (N <= 100,000) lines contains two integers h (h <= 1,000,000,000) and w (w <= 1,000,000,000) which means the height and width of Alice's card, then the following N lines means that of Bob's.

Output

For each test case, output an answer using one line which contains just one number.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2
2
1 2
3 4
2 3
4 5
3
2 3
5 7
6 8
4 1
2 5
3 4

Sample Output

1
2
1
2

题解

二维贪心 套路是先保持一维有序再来优化 有时候还需要点逆向思维 这题就是每次找最大的h和最大的w满足h2<=h1&&w2<=w1 那么先按h从小到大排序 找h很简单 但怎么快速找w那? 每次找到h后 把右边满足的w都放到一个容器里(右边也要排序 这样右边的每个都只会严格加一次 因为找下一个h时 容器里的都肯定满足要求) 容器必须满足有序 且插入操作为logn 查找也为logn c++有multiset java怎么办那 我们用TreeMap来模拟 key键就是w value为对应w的个数 非常巧妙 指得好好体会 其实都是Treap的变形
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.io.*;  
import java.util.*;
public class Main {
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
TreeMap<Integer,Integer>map=new TreeMap<Integer,Integer>();
int tt=sc.nextInt();
while(sc.hasNext()){
map.clear();
int n=sc.nextInt();
Node[]a=new Node[n];
Node[]b=new Node[n];
for(int i=0;i<n;i++){
int h=sc.nextInt();
int w=sc.nextInt();
a[i]=new Node(h,w);
}
for(int i=0;i<n;i++){
int h=sc.nextInt();
int w=sc.nextInt();
b[i]=new Node(h,w);
}
Arrays.sort(a);
Arrays.sort(b);
int t=0;
int count=0;
for(int i=0;i<n;i++){
while(t<n&&b[t].h<=a[i].h){
if(!map.containsKey(b[t].w)){
map.put(b[t].w, 1);
}else{
map.put(b[t].w, map.get(b[t].w)+1);
}
t++;
}
Integer find=map.floorKey(a[i].w);
if(find!=null){
int sum=map.get(find);
if(sum>=1){
count++;
if(sum>1){
map.put(find, map.get(find)-1);
}else{
map.remove(find);
}
}
}
}
pw.println(count);
pw.flush();
}

}
}
class Node implements Comparable<Node>{
int h;
int w;
Node(int a,int b){
h=a;
w=b;
}
@Override
public int compareTo(Node a) {
if(this.h>a.h)return 1;
if(this.h<a.h)return -1;
if(this.w>a.w)return 1;
if(this.w<a.w)return -1;
return 0;
}
}