類型： 排序
There are lots of number games for children. These games are pretty easy to play but not so easy to make. We will discuss about an interesting game here. Each player will be given N positive integer. (S)He can make a big integer by appending those integers after one another. Such as if there are 4 integers as 123, 124, 56, 90 then the following integers can be made – 1231245690, 1241235690, 5612312490, 9012312456, 9056124123 etc. In fact 24 such integers can be made. But one thing is sure that 9056124123 is the largest possible integer which can be made.
You may think that it’s very easy to find out the answer but will it be easy for a child who has just got the idea of number?
Input
Each input starts with a positive integer N (≤ 50). In next lines there are N positive integers. Input is terminated by N = 0, which should not be processed.
Output
For each input set, you have to print the largest possible integer which can be made by appending all theN integers.
題目大意：
輸入一串數字， 要求輸出有這些數字能拼成的最大的數字
分析與總結：
要讓一個數字最大的話，就要讓它的高位盡量的大。所以容易可以想到直接對這些數字按字典序（把他們看成字符串）從大到小進行排序，然後直接輸出了。
我真的這麼做了， 然後，就WA了。
原因在於， 例如這三個數： 12， 1211， 11， 直接排序後是1219, 12，11， 得到12191211， 但是正確的排序應該是12,1219,11， 為12121911。
進行排序時，如果位數相等的話，那麼直接可以字典序比較。 不相等的話，例如1219和12， 那麼就不能這樣了。那怎樣判斷呢？很明顯，這兩個數要麼第一個在前要麼就是第二個在前， 直接比較這兩種情況那個更大即可。
[cpp]
/*
* UVa 10905 - Children's Game
* Time : 0.176s (UVa)
* Author: D_Double
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
typedef string BigNum;
BigNum arr[52];
bool cmp (const string & a, const string & b){
if(a.size()==b.size()) return a > b;
string tmp1 = a+b , tmp2 = b+a;
return tmp1 > tmp2;
} www.2cto.com
int main(){
freopen("input.txt","r",stdin);
int n, i;
while(scanf("%d",&n), n){
for(i=0; i<n; ++i)
cin >> arr[i];
sort(arr, arr+n, cmp);
for(i=0; i<n; ++i)
cout << arr[i];
printf("\n");
}
return 0;
}
