POJ 1007 DNA Sorting

DNA Sorting

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 85118		Accepted: 34274

Description

One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence ``AACEDGG'' has only one inversion (E and D)---it is nearly sorted---while the sequence ``ZWQM'' has 6 inversions (it is as unsorted as can be---exactly the reverse of sorted).
You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness'', from ``most sorted'' to ``least sorted''. All the strings are of the same length.

Input

The first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (0 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.

Output

Output the list of input strings, arranged from ``most sorted'' to ``least sorted''. Since two strings can be equally sorted, then output them according to the orginal order.

Sample Input

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

Sample Output

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

解题思路：
这道题也是属于简单题，基本思路就是先算出每个DNA序列的逆序数，然后排个序输出（注意这里需要用稳定排序，我用了C++库的qsort，简单定义一下不处理‘==’的情况就可以了）。
求逆序数稍微有点技巧

代码：

 1 #include <iostream>
 2 #include <algorithm>
 3 
 4 /**************************************************
 5  * POJ 1007 DNA Sorting
 6  * author:樊列龙
 7  * 2014-12-16
 8  *************************************************/
 9 typedef struct DNA
10 {
11     int count;// 逆序数的个数
12     char DNAStr[110];
13 } DNA;
14 
15 int N;
16 int SIZE;
17 int countA,countC,countG;
18 
19 
20 /** 计算DNA字符串的逆序数  */
21 int getDNAInversionNumber(char* dnaStr)
22 {
23     int count = 0;
24     countA = countC = countG = 0;
25     for(int j = SIZE-1; j >= 0; j--)
26     {
27         switch(dnaStr[j])
28         {
29         case 'A':
30             countA++;
31             break;
32         case 'C':
33             countC++;
34             count += countA;
35             break;
36         case 'G':
37             countG++;
38             count += countA;
39             count += countC;
40             break;
41         case 'T':
42             count += countA;
43             count += countC;
44             count += countG;
45             break;
46         }
47     }
48     return count;
49 }
50 
51 int cmp(const void* a, const void* b)
52 {
53     DNA* DNA_A = (DNA*)a;
54     DNA* DNA_B = (DNA*)b;
55     return (DNA_A->count) - (DNA_B->count);
56 }
57 
58 int main()
59 {
60     using namespace std;
61     while(cin >> SIZE >> N)
62     {
63         DNA* dnas = new DNA[N];
64         for(int i = 0; i < N; i++)
65         {
66             cin >> dnas[i].DNAStr;
67             dnas[i].count = getDNAInversionNumber(dnas[i].DNAStr);
68         }
69 
70         qsort(dnas, N, sizeof(DNA), cmp);
71 
72         for(int i = 0; i < N; i++)
73         {
74             cout << dnas[i].DNAStr << endl;
75         }
76     }
77     return 0;
78 }