|
4thIIUCInter-University Programming Contest, 2005 |
|
|
A |
Children’s Game |
|
Input: standard input |
|
|
Problemsetter: Md. Kamruzzaman |
|
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 givenN 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 areN 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.
|
Sample Input |
Output for Sample Input |
|
4 |
9056124123 |
思路1：
贪心原则，为了让最终得到的数尽可能大，所以要让高位的数值尽可能大，直接按反字典序将数字串排序，并不正确，比如9和90排序后是90在前。
不过两个数字排列方式无非是一前一后，所以可以把两种排列的结果都比较下，这样做的的时间复杂度（只是两个数的比较）为O(3n)，同时要借助2n的空间（n为两数字的长度之和），但是写法很简单。
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool Cmp(const string &s, const string &t)
{
string st = s + t;
string ts = t + s;
return st > ts;
}
int main(void)
{
int n;
while (cin >> n)
{
if (n == 0) break;
vector<string> integers;
int i;
for (i = 0; i < n; ++i)
{
string str;
cin >> str;
integers.push_back(str);
}
sort(integers.begin(), integers.end(), Cmp);
for (i = 0; i < n; ++i)
{
cout << integers[i];
}
cout << endl;
}
return 0;
}
思路2：
假设如下数字串：
A: a1a2a3…an
B: b1b2b3…bm
AB: a1a2a3…anb1b2b3…bm
BA: b1b2b3…bma1a2a3…an
判断两数字串谁应该放在前面时（这里把字符串应该放在前面的称为较大数字串），有两种情况
1、 A和B能够直接比较出大小
当比较到ax和bx时（x<=n且x<=m），分出大小。
2、 需要对AB和BA的值进行比较
AB: a1a2a3…anb1b2b3…bm
BA: b1b2b3…bma1a2a3…an
比较到am和bm时（m<n），仍然相等，这时说明
a1a2a3…am= b1b2b3…bm①
接下来从AB式中的am+1和BA式中的a1进行比较
AB1:am+1am+2…anb1b2b3…bm
BA1:a1a2a3…an
用①式对BA1进行替换，得到
AB1:am+1am+2…anb1b2b3…bm
BA1:b1b2b3…bm am+1am+2…an
可以发现AB1和BA1与AB和BA的形式完全相同，只是下标的值不同而已，所以这个比较过程是递归的。
因为整个比较过程中，AB和BA中总是有一个下标在向后走，所以时间复杂度为O(n)（n为两数字串的长度之和）。
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool Cmp(const string &s, const string &t)
{
int i;
for (i = 0; i < s.length() && i < t.length(); ++i)
{
if (s[i] != t[i]) return s[i] > t[i];
}
if (s.length() == t.length())
{
return true;
}
else if (i == s.length())
{
return Cmp(s, t.substr(i));
}
else
{
return Cmp(s.substr(i), t);
}
}
int main(void)
{
int n;
while (cin >> n)
{
if (n == 0) break;
vector<string> integers;
int i;
for (i = 0; i < n; ++i)
{
string str;
cin >> str;
integers.push_back(str);
}
sort(integers.begin(), integers.end(), Cmp);
for (i = 0; i < n; ++i)
{
cout << integers[i];
}
cout << endl;
}
return 0;
}
欢迎转载，但请尊重作者，标明出处。