本文主要是介绍UVa 10905: Children's Game，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这真是一道有趣的题目，不知道别人怎么想，总之我觉得这题真的很有意思，值得一做。先附上题目：
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 the N integers.
| Sample Input | Output for Sample Input |
| 4 | 9056124123 |
分析问题后可以将问题表述成如下形式：
给出N个正数，使用某种方法将这N个数排序，使其排序后所连成的一个数值最大。
那么解决这个问题的关键就在于如何对这N个数进行排序？即排序的方法。
说到排序，我们可以使用qsort，但使用qsort的关键又在于其所调用的比较函数cmp，该函数cmp用于比较给出两个正数时，哪个数应当放在左面，哪个放在右面。
下面思考cmp函数如何实现，可以这样解决：对于两个正数i,j，我们写出其可以组合成的数，即ij和ji（注意这里ij表示将i和j按顺序写出时所组成的一个更大的数），那么比较ij和ji，就可以知道当我们将n个正数排序使之满足题意时，若其中包含有i和j，那么i一定出现在j的左边或是j一定出现在i的左边。
至此整个问题就分析完毕了，具体实现请参考我的解题代码，如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;char s[50][100];
int cmp(const void* i, const void* j)
{//判断i与j均可选时先选哪个，这里写成比较函数供qsort调用char *a = (char *)i;char *b = (char *)j;char sak,sbk;int k,lena=strlen(a),lenb=strlen(b);for(k=0; k<lena+lenb; k++){//循环判断数字ij和数字ji各位是否相同if(k<lena) sak=a[k];else sak=b[k-lena];if(k<lenb) sbk=b[k];else sbk=a[k-lenb];if(sak!=sbk) break;}if(k==lena+lenb) return 0; //ij与ji各位均相同，返回0表示相等else{if(sak<sbk) return 1; //ij的字典序较小，返回1表示先选i再选jelse return -1;}}
int main()
{int N;while(cin >> N && N!=0){for(int i=0; i<N; i++) cin >> s[i];qsort(s,N,sizeof(s[0]),cmp);for(int i=0; i<N; i++) cout << s[i]; cout << endl;}return 0;
}
这个算法的效率还不错，AC用时0.109秒，排名211。
这篇关于UVa 10905: Children's Game的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
