UVa 10905-Children's Game
テーマリンク:
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=113&page=show_problem&problem=1846
タイプ:並べ替え
The re are lots of number games for children.The e games are pretty to Playbut 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 apending those integers after one another.Such as if there 4 integers 123,124,56,90 then the follwing integers can made–1235690,12356909056124123 etc.In fact 24 such integers can be made.But one thing is sure that 9056124123 is the larget possible integer which can be made.
You may think that it’s very easury to find out the answer but will it be easure for a child who has just got the idea of number？
Input
Each input starts with a positive integer N （≦50）.In next lineas there re re N positive integers.Input is terminated by N = 0,which shoud not be processed.
Output
For each input set，you have to print the larget possible integer which can be made by apping all theN integers.
タイトルの大意:
一連の数字を入力して、これらの数字のつづり合わせができる最大の数字を出力することを要求します。
分析とまとめ：
一つの数字を最大にするには、その高位をできるだけ大きくします。これらの数字を直接字典順（文字列と見なしている）で大きいものから小さいものまで並べ替えて直接出力したと考えられます。
本当にそうしました。そして、WAにします。
その理由は、例えば、これらの3つの数：12、1211、11、 直接並べ替え後は1219、12、11で、1291211が得られます。 しかし、正確な順序は12,1219,11であり、12121221911であるべきである。
並べ替えを行う場合、桁数が等しい場合は、直接辞書の順序を比較することができます。同じでないと、例えば1219と12はこうはならない。どう判断しますか？この二つの数は一番前か二つ目の前か、この二つの場合を直接比較すればいいです。
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=113&page=show_problem&problem=1846
タイプ:並べ替え
The re are lots of number games for children.The e games are pretty to Playbut 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 apending those integers after one another.Such as if there 4 integers 123,124,56,90 then the follwing integers can made–1235690,12356909056124123 etc.In fact 24 such integers can be made.But one thing is sure that 9056124123 is the larget possible integer which can be made.
You may think that it’s very easury to find out the answer but will it be easure for a child who has just got the idea of number？
Input
Each input starts with a positive integer N （≦50）.In next lineas there re re N positive integers.Input is terminated by N = 0,which shoud not be processed.
Output
For each input set，you have to print the larget possible integer which can be made by apping all theN integers.
タイトルの大意:
一連の数字を入力して、これらの数字のつづり合わせができる最大の数字を出力することを要求します。
分析とまとめ：
一つの数字を最大にするには、その高位をできるだけ大きくします。これらの数字を直接字典順（文字列と見なしている）で大きいものから小さいものまで並べ替えて直接出力したと考えられます。
本当にそうしました。そして、WAにします。
その理由は、例えば、これらの3つの数：12、1211、11、 直接並べ替え後は1219、12、11で、1291211が得られます。 しかし、正確な順序は12,1219,11であり、12121221911であるべきである。
並べ替えを行う場合、桁数が等しい場合は、直接辞書の順序を比較することができます。同じでないと、例えば1219と12はこうはならない。どう判断しますか？この二つの数は一番前か二つ目の前か、この二つの場合を直接比較すればいいです。
/*
* 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;
}
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("
");
}
return 0;
}
—— ， 。
http://blog.csdn.net/shuangde800 ， By D_Double ( )