POJ：DNA Sorting 特殊的排序

POJ：DNA Sorting 特殊的排序2015-02-25Description

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

Sample Output

CCCGGGGGGAAACATGAAGGGATCAGATTTATCGATGCATTTTTGGCCAATTTGGCCAAA

很有意思的题目， POJ的题目都感觉相当好。

按照排序度的高低来排序，排序的排序？呵呵

因为数据的特殊性，所以本题可以计算逆序数的方法，可以0MS通过的，不过这里我使用的方法是：

1 merge sort来计算排序度

2 继续使用归并排序，排好最终序列

二次归并排序啊，呵呵，最终运行速度是16MS，做不到0MS，但是可以运行在无数据特殊性的情况下，通用性高。

#include <stdio.h>#include <iostream>#include <string>#include <vector>#include <algorithm>#include <math.h>using namespace std;struct DNA{string s;int n;DNA（int i = 0, string ss = ""） : n（i）, s（ss）{}bool operator<（const DNA &a） const{return n < a.n;}};string biMerge（string &L, string &R, int &c）{string s;unsigned i = 0, j = 0;while （ i < L.size（） && j < R.size（） ）{if （L[i] <= R[j]） s.push_back（L[i++]）;else{s.push_back（R[j++]）;c += L.size（） - i;}}if （ i < L.size（） ） s.append（L.substr（i））;elses.append（R.substr（j））;return s;}void biSort（string &s, int &c）{if （s.size（） < 2） return ;int mid = （（s.size（）-1）>>1）;//错误：写成s.size（）>>1string L（s.substr（0, mid+1））;biSort（L, c）;string R（s.substr（mid+1））;biSort（R, c）;s = biMerge（L, R, c）;}void DNASorting（）{int Len = 0, T = 0, c = 0;cin>>Len>>T;vector<DNA> dnas（T）;string t;for （int i = 0; i < T; i++）{cin>>t;dnas[i].s = t;c = 0;biSort（t, c）;dnas[i].n = c;}sort（dnas.begin（）, dnas.end（））;for （int i = 0; i < T; i++）{cout<<dnas[i].s<<endl;}}int main（）{DNASorting（）;return 0;}

From：csdn博客靖心