HOJ 1461 Gene Shuffle
http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1461
大概题意就是让你找出两串序列的最小公共集的集合。
Sample Input 2 10 1 2 3 6 4 7 5 8 9 10 3 2 1 4 5 6 7 8 10 9 5 2 1 4 5 3 2 4 5 3 1
Sample Output 1-3 4-7 8-8 9-10 1-1 2-5
由于他的序列是1-N，所以不妨创建一个1-N的结构体数组。每个元有两个元素分别记录他在两个序列中的位置，因为输出时依赖第一个序列中各元素的位置，所以用第一个数作为比较元进行快排。 不妨把每个结构体内部两个元素记作local1，local2，然后进行遍历，如果i位置local1 = local2，说明这个集合就是他的公共集。如果不相等，那么local2有可能是他的结果。 如果从local1到local2的每个元素都在此范围内，local1-local2便构成了一个最小公共集，否则继续取比原local2大的local2。 至此到结束便可得到结果。
#include<stdio.h> #include<stdlib.h> struct node{ int local1; int local2; }number[100000]; int cmp(const void *, const void *); int main(){ int i,T; int n,m; int min; int max; while(~scanf("%d",&T)){ while(T--){ scanf("%d",&n); for(i = 1; i <= n; i++){ scanf("%d",&m); number[m].local1 = i; } for(i = 1; i <= n; i++){ scanf("%d",&m); number[m].local2 = i; } qsort(&number[1],n,sizeof(number[1]),cmp); max = 0; min = 1; for(i = 1; i <= n; i++){ if(number[i].local1 == number[i].local2 && max == 0){ if(number[i].local1 != n){ printf("%d-%d ",number[i].local1,number[i].local2); min = i+1; } else printf("%d-%d\n",number[i].local1,number[i].local2); } else if(number[i].local2 > max) max = number[i].local2; else if(number[i].local1 == max && max != n){ printf("%d-%d ",min,max); min = i+1; max = 0; } } if(number[i-1].local1 != number[i-1].local2) printf("%d-%d\n",min,max); } } return 0; } int cmp(const void *a, const void *b){ struct node * c = (struct node *) a; struct node * d = (struct node *) b; return c->local1 - d->local1; }第一次写博客 以后会继续努力的..
