[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 6AACATGAAGGTTTTGGCCAATTTGGCCAAAGATCAGATTTCCCGGGGGGAATCGATGCAT

Sample Output

CCCGGGGGGAAACATGAAGGGATCAGATTTATCGATGCATTTTTGGCCAATTTGGCCAAA

Source East Central North America 1998

解题思路

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

实现代码;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 = 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)读取两个整数之后的回车符。

多看书，看好书。