2014年12月28日 星期日

2014/12/28 POJ 1007 DNA Sorting

/*
    學習重點:
    stable_sort
*/
// http://poj.org/problem?id=1007
#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;

string s[200];

bool cmp(string a, string b)
{
    int cnt = 0;

    for(int ai = 1; ai < a.size(); ai++)
        for(int aj = 0; aj < ai; aj++)
            if( a[ai] < a[aj] ) cnt++;

    for(int bi = 1; bi < b.size(); bi++)
        for(int bj = 0; bj < bi; bj++)
            if( b[bi] < b[bj] ) cnt--;

    return cnt < 0;
}

int main()
{
    int N, M;
    scanf("%d %d", &N, &M);

    for(int Mi = 0; Mi < M; Mi++)
        cin>>s[Mi];

    stable_sort(s, s+M, cmp);

    for(int Mi = 0; Mi < M; Mi++)
        cout<<s[Mi]<<endl;
}

沒有留言:

張貼留言