UVA 10905 Children's Game ( Ad hoc )

UVa Online Judge
挺有趣的一道題。一開始很直覺的直接比較字典序，WA了一波才想到問題在於長度相異的時候比較時，像是 cmp( 2, 27 ) 和 cmp( 2, 21 ) 是不同的，前者要回傳 false使成為 272，而後者要回傳 true使成為 221才會對。所以這時候應該要直接比較 a + b 還是 b + a 字典序大。後來看了人家 code才想到其實直接比較這件事就可以了，長度相同相異根本沒差。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50 + 5;

int n;
string num[MAXN];

bool cmp(const string &a, const string &b){
    for(int i = 0; i < a.size(); ++i){
        if( i >= b.size() ) return a + b > b + a;
        if( a[ i ] != b[ i ] ) return a[ i ] > b[ i ];
    }
    return a + b > b + a;
}

int main(){
    ios::sync_with_stdio( false );
    while( cin >> n && n ){
        for(int i = 0; i < n; ++i)
            cin >> num[ i ];
        sort( num, num + n, cmp );
        for(int i = 0; i < n; ++i)
            cout << num[ i ];// << " ";
        cout << endl;
    }
    return 0;
}