PKU 1007

DNA Sorting

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

bool    cmp( string a, string b );
int     sortedness( string s );

int main()
{
    int n, m;
    cin >> n >> m;

    vector<string> dna(m);
    for ( int i=0; i<m; i++ )
        cin >> dna[i];

    sort( dna.begin(), dna.end(), cmp );

    for ( int i=0; i<m; i++ )
        cout << dna[i] << endl;

    return 0;
}

bool cmp( string a, string b )
{
    return sortedness(a) < sortedness(b);
}

int sortedness( string s )
{
    int c = 0;

    for ( int i=0; i<(int)s.length(); i++ )
    for ( int j=i+1; j<(int)s.length(); j++ )
        if ( s[i] > s[j] )
            c++;
    
    return c;
}