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