POJ1007(DNA Sorting)

求逆序数的题。因为只有4种元素，所以可以直接统计排在某个元素前面且比它小的元素个数（用4个变量记录已出现的A,C,G,T的个数），复杂度为O(N)。若元素种类很多，可以使用树状数组进行类似基数排序的统计。

View Code

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define N 55
 4 #define M 105
 5 struct node
 6 {
 7     char s[N];
 8     int d;
 9 }node[M];
10 int a,c,g,t,len;
11 int cal(char s[])
12 {
13     int i,sum;
14     a=c=g=t=0;
15     sum=0;
16     for(i=0;i<len;i++)
17     {
18         switch(s[i])
19         {
20             case 'A':   a++,sum+=c+g+t; break;
21             case 'C':   c++,sum+=g+t;   break;
22             case 'G':   g++,sum+=t; break;
23             case 'T':   t++;    break;
24         }
25     }
26     return sum;
27 }
28 int cmp(const void*a,const void*b)
29 {
30     int x,y;
31     x=((struct node*)a)->d;
32     y=((struct node*)b)->d;
33     if(x!=y)    return x>y?1:-1;
34     else    return (struct node*)a-(struct node*)b;
35 }
36 int main()
37 {
38     int i,m;
39     while(~scanf("%d%d",&len,&m))
40     {
41         getchar();
42         for(i=0;i<m;i++)
43         {
44             gets(node[i].s);
45             node[i].d=cal(node[i].s);
46         }
47         qsort(node,m,sizeof(node[0]),cmp);
48         for(i=0;i<m;i++)    puts(node[i].s);
49     }
50     return 0;
51 }