一、題目信息
DNA Sorting
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 68122 Accepted: 27076
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
二、算法分析
1.枚舉法
本題實際就是計算一個序列的逆序數。關於逆序數的概念請自己查閱。最直接的方法就是對於序列中的每個元素，找在這個元素之後，並比這個元素小的元素數，我們暫且稱這個數為一個元素的的逆序數。一個序列的所有元素逆序數的宗和，就是一個序列的逆序數。
枚舉法的求一個序列的逆序數時間復雜度是O(n^2)，再加上對序列排序，時間復雜度最低也是O(n^2*mlogm)。
另外注意的是，由於題目要求Since two strings can be equally sorted, then output them according to the orginal order.也即是，兩個逆序數相同的序列，輸出的順序應該跟輸入的順序是一樣的。這就要求對序列的排序，應該采用穩定排序。用C++STL中的算法stable_sort就可以了。
2.歸並排序
就單純求逆序數來說，用歸並排序是一個較好的方法，在歸並排序的過程中，加入記錄元素交換次數代碼就可以求出逆序數。時間復雜度能降到O(nlogn)。總的時間復雜度能降到O(nlogn * mlogm)。
三、參考代碼
1.枚舉法C++代碼
[cpp]
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <windows.h>
using namespace std;
size_t countUnsortedness(const string &s)
{
int sum = 0;
for(int i = 0;i < s.size();i++)
for(int j = i+1; j <s.size(); j++)
if (s[j] < s[i] )
sum++;
return sum;
}
bool comp(const string &s1,const string &s2)
{
return countUnsortedness(s1) < countUnsortedness(s2) ? true : false;
}
int main()
{
vector< string > DNAs;
int n,m;
cin >> n >> m;
for(string s;m--;cin>>s,DNAs.push_back(s));
stable_sort(DNAs.begin(),DNAs.end(),comp);
for(int i = 0; i < DNAs.size(); i++)
cout << DNAs[i] << endl;
system("pause");
return 0;
}
2.歸並排序C++代碼
