DNA SortingTime Limit: 1000MS           Memory Limit: 10000KTotal Submissions: 83069           Accepted: 33428DescriptionOne 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. InputThe 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.OutputOutput 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 Input10 6AACATGAAGGTTTTGGCCAATTTGGCCAAAGATCAGATTTCCCGGGGGGAATCGATGCATSample OutputCCCGGGGGGAAACATGAAGGGATCAGATTTATCGATGCATTTTTGGCCAA TTTGGCCAAA

 

 

解法一：逆序数+快排（对cmp的完美诠释，原谅我刚刚学）+结构体（第一次在OJ用结构体）——

由于这道题目的数据量不算太大，直接用朴素的求逆序数绝对可以；

逆序数就是看这个数前面有多少个数比当前的数大，这里直接用了一个二重循环；

#include 
      
           #include 
       
            #include 
        
             using namespace std;    typedef struct f{        int num;        string w;    }data;    bool cmp( data a, data b ){        return a.num < b.num;    }    int main(){        int i, len, n, j, k;        cin>>len>>n;        data *s = new data[n];        for(i = 0; i < n; i++){            s[i].num = 0;            cin>>s[i].w;            for(j = 1; j < len; j++)                for(k = 0; k < j; k++)                    if(s[i].w[j] < s[i].w[k])//求逆序数                        s[i].num++;        }        sort(s, s+n, cmp);        for(i = 0; i < n; i++)            cout<
         
          <
         
        
       
      

解法二：这里进行求逆序数的有一种方法很巧妙，因为题目中只有4个字母，所以就用到了这种特殊性，我们可以得到O(n)求逆序数的方法；

#include 
      
       #include 
       
        #include 
        
         using namespace std;struct node{    char s[100];//储存DNA序列    int sum;//储存每个DNA序列的逆序数}a[100];bool cmp(node x,node y)//比较函数{    return x.sum
         
          = 0; i--) {                switch (str[i]) {                        case 'A':                                a[1]++;                                a[2]++;                                a[3]++;                                break;                        case 'C':                                a[2]++;                                a[3]++;                                cnt += a[1];                                break;                        case 'G':                                a[3]++;                                cnt += a[2];                                break;                        case 'T':                                cnt += a[3];                }        }        return cnt;}int main(){    int m,n,i,j;    scanf("%d%d",&n,&m);    for(i=0;i