http://acm.hdu.edu.cn/showproblem.php?pid=4268
这道题把，比赛时想到了是贪心 ，而且是 贪的方法 和看的解题报告差不多 但是，比赛时，我们找到了 几个 例子觉的不对，就没有 往下想 ，汗。。。。。。。。。。。。
明显的贪心 ：
先按第一维排序，然后第二维
然后对a的每个i，找出小于a[i].h的b.h，将对应的w塞到集合里
刚才已经保证了第一维满足了
然后贪心的从集合里面找a[i]能覆盖的最大的w
然后对a的每个i，找出小于a[i].h的b.h，将对应的w塞到集合里
刚才已经保证了第一维满足了
然后贪心的从集合里面找a[i]能覆盖的最大的w
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-12
15 #define inf 100000000
16 #define mx 1<<60
17
18 const double pi = acos(-1.0);
19 const int maxn = 101000;
20 typedef __int64 ll;
21 using namespace std;
22 struct node
23 {
24 int h;
25 int w;
26 int type;
27 }a[maxn*2];
28 multiset<int>s;
29 int cmp(node a,node b)
30 {
31 if(a.h != b.h) return a.h < b.h;
32 else
33 if(a.w!=b.w) return a.w < b.w ;
34 else return a.type > b.type ;
35
36 }
37 int main()
38 {
39 int t,n,i;
40 scanf("%d",&t);
41 while(t--)
42 {
43 scanf("%d",&n);
44 for(i=0 ; i < n;i++)
45 {
46 scanf("%d %d",&a[i].h,&a[i].w);
47 a[i].type = 0;
48 }
49 for(i = n ; i < 2*n;i++)
50 {
51 scanf("%d %d",&a[i].h,&a[i].w);
52 a[i].type = 1;
53 }
54
55 sort(a,a+2*n,cmp);
56 int ans = 0;
57 s.clear();
58 for(i = 0 ; i < 2*n;i++)
59 {
60 if(a[i].type == 1)
61 {
62 s.insert(a[i].w);
63
64 }
65 else
66 {
67 if(!s.empty())
68 {
69 if(*s.begin() <= a[i].w)
70 {
71 multiset <int>::iterator it = s.upper_bound(a[i].w);
72 it--;
73 ans++;
74 s.erase(it);
75
76 }
77
78
79 }
80 }
81 }
82 printf("%d\n",ans);
83
84 }
85 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-12
15 #define inf 100000000
16 #define mx 1<<60
17
18 const double pi = acos(-1.0);
19 const int maxn = 101000;
20 typedef __int64 ll;
21 using namespace std;
22 struct node
23 {
24 int h;
25 int w;
26 int type;
27 }a[maxn*2];
28 multiset<int>s;
29 int cmp(node a,node b)
30 {
31 if(a.h != b.h) return a.h < b.h;
32 else
33 if(a.w!=b.w) return a.w < b.w ;
34 else return a.type > b.type ;
35
36 }
37 int main()
38 {
39 int t,n,i;
40 scanf("%d",&t);
41 while(t--)
42 {
43 scanf("%d",&n);
44 for(i=0 ; i < n;i++)
45 {
46 scanf("%d %d",&a[i].h,&a[i].w);
47 a[i].type = 0;
48 }
49 for(i = n ; i < 2*n;i++)
50 {
51 scanf("%d %d",&a[i].h,&a[i].w);
52 a[i].type = 1;
53 }
54
55 sort(a,a+2*n,cmp);
56 int ans = 0;
57 s.clear();
58 for(i = 0 ; i < 2*n;i++)
59 {
60 if(a[i].type == 1)
61 {
62 s.insert(a[i].w);
63
64 }
65 else
66 {
67 if(!s.empty())
68 {
69 if(*s.begin() <= a[i].w)
70 {
71 multiset <int>::iterator it = s.upper_bound(a[i].w);
72 it--;
73 ans++;
74 s.erase(it);
75
76 }
77
78
79 }
80 }
81 }
82 printf("%d\n",ans);
83
84 }
85 }