题目描述：设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
程序输入：n个数程序输出：联接成的多位数
例如：n=2时，2个整数32，321连接成的最小整数为：32132，n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
[题目要求]1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算法。2. 给出算法的时间空间复杂度。3. 证明你的算法。（非常重要）
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <iostream>
#include <iterator>
#include <sstream>
using namespace std;
struct Less
{
bool operator()(long i, long j)
{
static stringstream ss;
ss.clear();
ss<<i<<" "<<j;
string stri,strj;
ss>>stri>>strj;
return (i*powl(10,strj.length())+j) < (j*powl(10,stri.length()) +i);
}
};
int main()
{
long x[] = {565, 56, 5655};
sort(x, x+3, Less());
copy(x, x+3, ostream_iterator<long>(cout));
}证明：
假设： 排序后的 a0a1...an不是最小的，那么存在a0a1...ajai....an<a0a1...an,且ajai > aiaj.
那么交换ajai会使可以使a0a1...an更小，与假设a0a1...ajai....an<a0a1...an矛盾。
证明完毕。
posted on 2009-06-04 23:49
尹东斐 阅读(691)
评论(2) 编辑 收藏 引用