题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1677
题意:
玩俄罗斯套娃,问最后至少还剩几个。
题解:
这题可以和拦截导弹做对比,因为这里是二维的,按w递减h递增的方式来保证在保存的序列中按h升序来排的,从而为二分查找打下基础。
否则,如果按h降序排,保存的序列就会无序,二分结果自然不正确了。
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5
6 const int maxn = 20000 + 10;
7
8 struct Node {
9 int w, h;
10 bool operator < (const Node& tmp) const {
11 return w < tmp.w&&h < tmp.h;
12 }
13 }arr[maxn], dp[maxn];
14
15 bool cmp(Node& n1, Node& n2) {
16 return n1.w > n2.w || (n1.w == n2.w) && (n1.h<n2.h);
17 }
18
19 int n;
20
21 int main() {
22 int tc;
23 scanf("%d", &tc);
24 while (tc--) {
25 scanf("%d", &n);
26 for (int i = 0; i < n; i++) {
27 scanf("%d%d", &arr[i].w,&arr[i].h);
28 }
29 sort(arr, arr + n, cmp);
30 int ans = 0;
31 dp[++ans] = arr[0];
32 for (int i = 1; i < n; i++) {
33 //dp按w降序,h升序排的!!!为了维护h是升序排的,必须保证输入中w相等时h按升序排而不是降序
34 int low = 0, hig = ans;
35 while (low + 1 < hig) {
36 int mid = low + (hig - low) / 2;
37 if (arr[i] < dp[mid]) hig = mid;
38 else low = mid;
39 }
40 if (arr[i] < dp[hig]) {
41 dp[hig] = arr[i];
42 }
43 else {
44 dp[++ans] = arr[i];
45 }
46 }
47 printf("%d\n", ans);
48 }
49 return 0;
50 }