題目描述：設(shè)有n個(gè)正整數(shù)，將它們聯(lián)接成一排，組成一個(gè)最小的多位整數(shù)。
程序輸入：n個(gè)數(shù)程序輸出：聯(lián)接成的多位數(shù)
例如：n=2時(shí)，2個(gè)整數(shù)32，321連接成的最小整數(shù)為：32132，n=4時(shí)，4個(gè)整數(shù)55，31，312, 33 聯(lián)接成的最小整數(shù)為：312313355
[題目要求]1. 給出偽代碼即可，請(qǐng)給出對(duì)應(yīng)的文字說(shuō)明，并使用上面給出的例子試驗(yàn)?zāi)愕乃惴ā?. 給出算法的時(shí)間空間復(fù)雜度。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));
}證明：
假設(shè)： 排序后的 a0a1...an不是最小的，那么存在a0a1...ajai....an<a0a1...an,且ajai > aiaj.
那么交換ajai會(huì)使可以使a0a1...an更小，與假設(shè)a0a1...ajai....an<a0a1...an矛盾。
證明完畢。
posted on 2009-06-04 23:49
尹東斐 閱讀(710)
評(píng)論(2) 編輯 收藏 引用