[POJ] DNA Sorting

Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 83069
Accepted: 33428

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'' toleast 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

Source
East Central North America 1998

解题思路

首先求出逆序数，然后对逆序数进行排队，最后输出排序后的DNA序列。对于求逆序数，只需对序列进行遍历，找出本应出现在某字符之后，却出现在了它之前的字符数即可（顺序为ACGT）。

实现代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef struct node
{
    char s[100];
    int value; //逆序对数
}DNA;

bool cmp(DNA d1, DNA d2)
{
    return d1.value < d2.value;
}

//获取逆序对数
int rev_cnt(char *ch)
{
    int cnt[4] = {0};
    int reverse_cnt = 0;
    int i = 0;
    while(ch[i])
    {
        switch(ch[i])
        {
        case 'A':
            cnt[0]++;
            reverse_cnt += cnt[1] + cnt[2] + cnt[3];
            break;
        case 'C':
            cnt[1]++;
            reverse_cnt += cnt[2] + cnt[3];
            break;
        case 'G':
            cnt[2]++;
            reverse_cnt += cnt[3];
            break;
        case 'T':
            cnt[3]++;
            break;
        }
        i++;
    }

    return reverse_cnt;
}

void sort(DNA *d, int len)
{
    for (int i = 0; i < len - 1; i++)
    {
        int index = i;
        for (int j = i + 1; j < len; j++)
        {
            if (d[j].value < d[index].value)
            {
                index = j;
            }
        }

        if (index != i)
        {
            //DNA temp;
            //memcpy(&temp, &d[i], sizeof(d[i]));
            //memcpy(&d[i], &d[index], sizeof(d[index]));
            //memcpy(&d[index], &temp, sizeof(temp));
            DNA temp = d[i];
            d[i] = d[index];
            d[index] = temp;
        }
    }
}

int main()
{
    int m, n;
    scanf("%d%d", &m, &n); //m为输入字符长度，n为数据组数
    DNA *d = new DNA[n];
    int i = 0;
    while(i < n)
    {
        scanf("%s", d[i].s);
        d[i].value = rev_cnt(d[i].s);
        i++;
    }

    sort(d, d + n, cmp);
    //sort(d, n);自定义排序函数
    for (int i = 0; i < n; i++)
    {
        cout<<d[i].s<<endl;
    }

    delete [] d;
    return 0;
}

排序部分可以用<algorithm>里面的sort，也可以是自定义的。输入部分如果将scanf改为cin.getline(d[i].s, m+1)则需要先用一个scanf("%c", &c)读取两个整数之后的回车符。