【问题描述】

设有n个正整数，将他们连接成一排，组成一个最大的多位整数。

【资料图】

当n=3的时候，3个整数13、312、343，连成的最大整数为34331213。

当n=4的时候，4个整数7、13、4、246，连成的最大整数为7424613。

输入 n

n个数

输出   连成的多位数

算法分析：

如果我们将输入的数据按照从大到小的排序，很容易找到反例，比如12、121，就会找到12112。但是两数还可以组合成12121。

那么从小到大排序呢？12、123两个数，可以组合成12123，但是两个数还可以组合成12312。走到这里，我们陷入了绝境。是不是不能使用贪心算法呢？找不到合适的贪心策略。

真的就走投无路了吗？

仔细观察，将数字转换为字符串，比较字符串的大小。

将结果从大到小排序。

13、312、343排序后的顺序为343、312、13     将其组合成数字即可    34331213

7、13、4、246排序后的顺序为7、4、246、13  将其组合成数字7424613

以上就是解题的贪心策略。找到策略。

代码实现如下：

/*combile_max.cpp*/

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int compare_func(const string &p1, const string &p2){

return (p1)>=(p2);

}

int main(void){

int n;

string sv;

cout<<"input number n:"<<endl;

cin>>n;

vector<string> s;

for(int i=0;i<n;i++){

cin>>sv;

s.push_back(sv);

}

sort(s.begin(), s.end(), compare_func);

for(auto it=s.begin(); it != s.end(); it++)

cout << *it;

cout << endl;

return 0;

}

编译、链接、运行结果如下：

cargo@cargo-virtual-machine:~$ g++ combile_max.cpp  -std=c++11

cargo@cargo-virtual-machine:~$ ./a.out

input number n:

3

13

312

343

34331213

cargo@cargo-virtual-machine:~$ ./a.out

input number n:

4

7

13

4

246

7424613

关键词：