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