POJ 1007 解题报告 DNA Sorting

 

#include <iostream>
#include <string>
#include <map>

using namespace std;

class DNA{
public:
	string strDNA;
	DNA(string);
};

DNA::DNA(string s)
{
	strDNA = s;
}

int calculateInversionsNum(const string&);
bool operator<(const DNA&, const DNA&);

int main ()
{
	string str;

	int iNum;
	int iLength;

	cin >> iLength >> iNum;

	map<DNA, int> mDna;

	while (iNum--)
	{
		cin >> str;
		DNA d = DNA(str);
		++mDna[d];
	}

	map<DNA, int>::iterator iterI = mDna.begin();
	while(iterI != mDna.end())
	{
		while (iterI->second --)
		{
			cout << iterI->first.strDNA << endl;
		}
		iterI ++;
	}

	return 0;
}

bool operator<(const DNA& dL, const DNA& dR)
{
	if(calculateInversionsNum(dL.strDNA) < calculateInversionsNum(dR.strDNA))
	{
		return true;
	}
	else
	{
		return false;
	}
}

int calculateInversionsNum(const string& str)
{
	int i = 0;
	int iInversionsNum = 0;
	while (i < str.size() - 1)
	{
		int iCountRepeat = 1;
		while (str[i] == str[i + 1])
		{
			iCountRepeat ++;
			i++;
			if (i == str.size() - 1)
			{
				return iInversionsNum;
			}
		}

		int j = i;
		int iAdd = 0;
		while (j < str.size())
		{
			if (str[i] > str[j])
			{
				iAdd ++;
			}
			j ++;
		}
		iInversionsNum += iCountRepeat * iAdd;
		i ++;
	}
	return iInversionsNum;
}