#include <iostream>

using namespace std;

int main()
{
	char *dna, *a, *d, **ind, c[5];
	int n, m, i, j, k, v, t, s, p;

	cin>>n>>m; // Read n&m;

	t = m*(n+1);
	p = n*(n-1)/2;
	s = m*p;

	dna = new char[t];	// All DNA data will be stored here
	d = new char[s];	// DNA index in 'dna' (The max inversions of one DNA is n*(n-1), and there are m DNAs)
	ind = new char *[p];	// Pointers to each inversion value space in d
	memset(d, -1, s);	// Init each d to -1
	ind[0] = d;
	for(i=1; i<p; i++)
	{
		ind[i] = ind[i-1] + m;
	}// Now ind[0] pointed to inversion 0, ind[1] to 1, ...

	a = dna;
	for(i=0; i<m; i++)
	{
		cin>>dna+(n+1)*i;
		a += n+1;
	}// Read all DNAs

	for(i=0; i<t; i++)	// Replace ACGT with 1234, just for easy to compute.
	{
		switch(dna[i])
		{
			case 'A':
				dna[i] = 1;
				break;
			case 'C':
				dna[i] = 2;
				break;
			case 'G':
				dna[i] = 3;
				break;
			case 'T':
				dna[i] = 4;
				break;
			default:
				break;
		}
	}
	a = dna;
	for(i=0; i<m; i++)
	{
		memset(c, 0, 5);	// Init c
		v = 0;
		for(j=0; j<n; j++)
		{
			c[a[j]]++;	// c[4] is the count of T, c[3] is G, 2 is C, 1 is A, 0 is not used
			for(k=4; k>a[j]; k--)
			{
				v += c[k];
			}// Now v is the inversion of this DNA
		}
		*(ind[v]) = i;
		ind[v]++;	// Add this DNA to the v inversion space, and new inversion index to this space move 1 char right
		a += n+1;
	}// Now values!=-1 in d is the ordered DNA indexes

	for(i=0; i<t; i++)	// Back to ACGT from 1234
	{
		switch(dna[i])
		{
			case 1:
				dna[i] = 'A';
				break;
			case 2:
				dna[i] = 'C';
				break;
			case 3:
				dna[i] = 'G';
				break;
			case 4:
				dna[i] = 'T';
				break;
			default:
				break;
		}
	}

	for(i=0; i<s; i++)
	{
		if(d[i] >= 0)	// If the index is not -1
		{
			cout<<dna + d[i]*(n+1)<<endl;	//The DNA
		}
	}

	delete[] dna;
	delete[] d;
	delete[] ind;
	return 0;
}

• Re:一个O(N)的算法, 不过老是WA, 大家帮忙看一下, 多谢 (407) Wonlay 2006-09-08 14:37:23