問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1828思路:
按照坐標(biāo)從上到下、從左到右排序
首先想到的是O(n^2)的算法，時間需要1600+MS
然后，發(fā)現(xiàn)其實(shí)在排序之后只要從后向前掃描一遍即可得出結(jié)果
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 50001
5 int n;
6 struct Point {
7 int x, y;
8 }points[MAX_LEN];
9
10 int
11 compare(const void *arg1, const void *arg2)
12 {
13 struct Point *a = (struct Point *)arg1;
14 struct Point *b = (struct Point *)arg2;
15 if(a->x == b->x)
16 return a->y - b->y;
17 return a->x - b->x;
18 }
19
20 int
21 main(int argc, char **argv)
22 {
23 int i, j, cnt, ymax;
24 while(scanf("%d", &n)!=EOF && n) {
25 for(i=0; i<n; i++)
26 scanf("%d %d", &points[i].x, &points[i].y);
27 qsort(points, n, sizeof(struct Point), compare);
28 /* O(n^2) AC 1600+MS
29 cnt = 0;
30 for(i=0; i<n; i++) {
31 for(j=i+1; j<n; j++) {
32 if(points[j].y >= points[i].y)
33 break;
34 }
35 if(j == n)
36 ++cnt;
37 }
38 */
39 /* O(nlgn) AC 235MS */
40 cnt = 1;
41 ymax = points[n-1].y;
42 for(i=n-2; i>=0; i--) {
43 if(ymax < points[i].y) {
44 ++cnt;
45 ymax = points[i].y;
46 }
47 }
48 printf("%d\n", cnt);
49 }
50 }