///// 好一段时间没做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 1000000int 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:6726500 633415724 1916929358 1147824464 2696228145 570516827 23281491 996111942 29955436 482714604 32391153 390212382 29218716 1742119895 1971821726 544711538 1477119912 186926299 256679894 1703523811 2870330333 313224664 176737711 151416868 2825327644 2554732757 3266212859 200379741 8723778 275293035 123161842 2219030106 2888942 904022648 1926423805 274466729 1589015350 2437031101 150063548 2439312623 1962919954 2408411840 187567376 496626308 1393132439 1694411323 2462621538 55372082 1611816541 2292931115 483329658 46399930 227042306 1397722386 3167328745 502119072 269245829 627015573 2677716512 509713290 2398618636 916124767 2235515574 2365512052 40311150 2735021724 169413430 13966718007 3019115457 1133727753 1228714945 1038332209 890924221 97586422 185884613030 2750629168 1641332591 9001655 187626359 1741020537 276246483 215484041 2759524350 360230836 1029111020 937424021 459623199 2734824484 196684734 82811999 5327938 264183788 6900467 1812714893 372822483 246482421 178076617 143109514 228137616 1430917451 189355249 2060031556 1651930303 2279811008 622432609 584432702 1498920485 319514343 30931587 305239503 2931425200 74486618 1345819796 2058015281 1479820798 1958927157 2800923622 2047212292 1853824179 603829657 18190Sample output:14410

评论