UVA_10905
我们不妨先定义一个大于号“》”：对于字符串a，b，如果有a》b就表示ab的字典序要大于ba的字典序。
假设：如果有a》b，且b》c，那么就有a》c。
如果这个假设满足，那么N个字符串就可以按》的关系排成一排，这时拼成的字符串就是字典序最大的（同时也是值最大的，因为最终拼成的字符串的长度是一定的，所以值的大小关系和字典序的大小关系是相同的）。
下面用反证法证明为什么这样拼成的字符串的字典序一定是最大的：如果最终拼成的字符串不是这样的，那么就一定存在相邻的两个字符串a、b不满足a》b，那么我们可以交换a、b的顺序，这样得到的结果不会变得更差。于是我们不停的交换不满足a》b的两个相邻的a、b，直到变成N个字符串是按》的关系排成一排为止，这样得到的结果不会变得更差。因此，可以保证这样拼成的字符串字典序是最大的。
当然，这样的贪心思路是依赖于上文中字体加粗的“假设”部分的。如果不能证明这个假设是正确的，那么就没办法说明这个贪心是正确的（比如如果存在a》b，b》c且c》a，那么对于acb来讲，到底是变成cab更好，还是变成abc更好呢？这恐怕就说不清了吧……）。但是我暂时没证明出“假设”的部分，稍后补上……
*上述讨论默认N个字符串是不同的，如果有相同的字符串，处理和证明的过程也基本相同，所以就没再讨论有相同字符串的情况了。
#include<stdio.h> #include<string.h> #include<string> #include<algorithm> #include<iostream> std::string a[110]; bool cmp(std::string a, std::string b) { return (a + b).compare(b + a) > 0; } int main() { int N; while(scanf("%d", &N), N) { for(int i = 0; i < N; i ++) std::cin >> a[i]; std::sort(a, a + N, cmp); for(int i = 0; i < N; i ++) std::cout << a[i]; std::cout << std::endl; } return 0; }