///// 好一段时间没做ACM题了,AC一道题都难了,看来以后还得经常练手...... , 贴一道简单的题
| Sequence |
| Time Limit: 2000ms, Special Time Limit:5000ms, Memory Limit:65536KB |
| Problem description |
Giving a collection S of points on two dimension plane. (S = {(x0,y0), (x1,y1), ... }) We define a point is greater than another point when all its coordinate on two axis are both greater than or equel to another one. Namely, p is greater than q when xp ≥ xq and yp ≥ yq. A sequence is a list points < p1, p2, ... > satisfy that i < j => pi is greater than pj. You can use the elements in S to construct sequences, how many sequences needed to cover a S at least? |
| Input |
The input consists of several test cases. Each test case start with a line containing a number n(0 < n ≤ 1000000), the number of points in S. Then n lines follows, each line containing two number, xi, yi(0 ≤ xi, yi ≤ 100000), the position of point i. The input end with EOF. |
| Output |
You have to print minium number of sequences needed to cover S in a single line for each case. |
| Sample Input |
4 1 1 2 2 3 3 4 4 4 1 5 2 6 2 3 3 4 |
| Sample Output |
1 2 |
题目意思, 将所给的数对,按升序排列成子序列,求最少的字序列数目对示例里的第二组数据就是{ (1 5), (2 6) }, {(2 3), (3 4)} 两个子序列, 子序列{ p1, p2, p3,...} 要满足i > j 时pi >= pj
///// my code , WA了很久才得到的......
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000002
struct ND{
int a, b;
}node[MAX];
int myCmp(const struct ND* a, const struct ND* b){
if(a->a > b->a)
return 1;
if(a->a < b->a)
return -1;
return (a->b>=b->b ? 1 : -1);
}
int main(){
int n,i,j,k;
while(scanf("%d",&n)!=EOF){
for(i=0; i<n; i++)
scanf("%d %d",&node[i].a,&node[i].b);
qsort(node,n,sizeof(struct ND),myCmp);
node[0].a = node[0].b;
for(j=1,i=1; i<n; i++){
for(k=0; k<j; k++){
if(node[i].b >= node[k].a){
node[k].a = node[i].b;
break;
}
}
if(k>=j)
node[j++].a = node[i].b;
}
printf("%d\n",j);
}
return 0;
}
/////// 产生测试数据的程序
#include <stdio.h>
#include <stdlib.h>
#define MAX_TEST 20
#define MAX_PAIR 1000000
int main(){
int n,m,i,j;
FILE *fp;
fp=fopen("data.txt","w+");
n = rand()%MAX_TEST;
if(n<10)
n=20;
for(i=0; i<n; i++){
m=rand()%MAX_PAIR;
if(m==0)
m=2;
fprintf(fp,"%d\n",m);
for(j=0; j<m; j++)
fprintf(fp,"%d %d\n",rand()%100000,rand()%100000);
}
fclose(fp);
return 0;
}//// 测试数据及测试结果
Sample In:
67
26500 6334
15724 19169
29358 11478
24464 26962
28145 5705
16827 23281
491 9961
11942 2995
5436 4827
14604 32391
153 3902
12382 292
18716 17421
19895 19718
21726 5447
11538 14771
19912 1869
26299 25667
9894 17035
23811 28703
30333 31322
4664 17673
7711 15141
6868 28253
27644 25547
32757 32662
12859 20037
9741 8723
778 27529
3035 12316
1842 22190
30106 288
8942 9040
22648 19264
23805 27446
6729 15890
15350 24370
31101 15006
3548 24393
12623 19629
19954 24084
11840 18756
7376 4966
26308 13931
32439 16944
11323 24626
21538 5537
2082 16118
16541 22929
31115 4833
29658 4639
9930 22704
2306 13977
22386 31673
28745 5021
19072 26924
5829 6270
15573 26777
16512 5097
13290 23986
18636 9161
24767 22355
15574 23655
12052 4031
1150 27350
21724 16941
3430 13966
7
18007 30191
15457 11337
27753 12287
14945 10383
32209 8909
24221 9758
6422 18588
46
13030 27506
29168 16413
32591 900
1655 18762
6359 17410
20537 27624
6483 21548
4041 27595
24350 3602
30836 10291
11020 9374
24021 4596
23199 27348
24484 19668
4734 8281
1999 53
27938 26418
3788 6900
467 18127
14893 3728
22483 24648
2421 17807
6617 14310
9514 22813
7616 14309
17451 18935
5249 20600
31556 16519
30303 22798
11008 6224
32609 5844
32702 14989
20485 3195
14343 3093
1587 30523
9503 29314
25200 7448
6618 13458
19796 20580
15281 14798
20798 19589
27157 28009
23622 20472
12292 18538
24179 6038
29657 18190
Sample output:
14
4
10
评论