POJ 1007: DNA Sorting

解题要点 1: 建立恰当的数据结构.

建立一个具有下列功能的类:

1. 能够自动计算和存储逆序数.
2. 拥有 operator<() 重载函数, 判别依据为逆序数的多少.

解题要点 2: 选择恰当的排序函数.

必须使用稳定排序, 以确保逆序数相同的字符串能按照输入的顺序输出.

代码如下:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class Dna {
    public:
        string dnaCode;
        int unsortedness;
        Dna( const string& dna_ );
        bool operator<( const Dna& dna_ ) const;
};

Dna::Dna( const string& dna_ ) : dnaCode( dna_ ), unsortedness(  ) {
    for( string::const_iterator pos1 = dnaCode.begin(); pos1 < dnaCode.end(); ++pos1 ) {
        for( string::const_iterator pos2 = pos1 + ; pos2 < dnaCode.end(); ++pos2 ) {
            if( *pos1 > *pos2 ) {
                ++unsortedness;
            }
        }
    }
}

bool Dna::operator<( const Dna& dna_ ) const {
    return unsortedness < dna_.unsortedness;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<Dna> dnaVec;
    string tmp;
    while( m-- >  ) {
        cin >> tmp;
        dnaVec.push_back( Dna( tmp ) );
    }
    stable_sort( dnaVec.begin(), dnaVec.end() );
    for( vector<Dna>::const_iterator pos = dnaVec.begin(); pos < dnaVec.end(); ++pos ) {
        cout << pos->dnaCode << endl;
    }
}