POJ - DNA Sorting 特殊的排序

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

很有意思的题目， 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));
	else	s.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()>>1

	string 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;
}