算法分析
此题很容易想到使用贪心法。
把整数按从大到小的顺序连接起来，测试题目的例子也都符合，但最后测试的结果却不全对。按这种贪心标准，我们很容易找到反例：12，121 应该组成12121而非12112，那么是不是相互包含的时候就从小到大呢？也不一定，如：12，123 就是12312而非12112,这样情况就有很多种了。
是不是此题不能用贪心法呢？
其实此题是可以用贪心法来求解，只是刚才的贪心标准不对，正确的贪心标准是：先把整数化成字符串，然后再比较a+b和b+a，如果a+b>b+a，就把a排在b的前面，反之则把a排在b的后面。
举例说明正常的字符串比较缺陷！如：A=’321’，B=’32’，按照标准的字符串比较规则因为A>B，所以A+B > B+A ，而实际上'32132' < '32321'。
所以，自定义一种字符串的比较规则：
如果A+B>B+A,则我们认为A>B。
且可以证明：如果A+B>=B+A,B+C>=C+B,则一定有：A+C>=C+A。
这样一来，程序就很简单了。分3步：
（1）先把n个数字转换成字符串存储；
（2）按照自定义的规则把n个字符串从大到小排序；
（3）依次输出这些字符串。
代码
1 #include <iostream> 2 #include <sstream> 3 #include <string> 4 #include <vector> 5 6 using namespace std; 7 8 string int2str(int num) { 9 stringstream ss; 10 ss << num; 11 return ss.str(); 12 } 13 14 int main() 15 { 16 vector<string> v; 17 int num; 18 19 while (cin>>num) { 20 v.push_back(int2str(num)); 21 } 22 for (unsigned int i = 0; i < v.size()-1; i++) { 23 for (unsigned int j = 0; j < v.size()-i-1; j++) { 24 if ((v[j] + v[j+1]) < (v[j+1]+v[j])) { 25 swap(v[j], v[j+1]); 26 } 27 } 28 } 29 30 for (unsigned int i = 0; i < v.size(); i++) { 31 cout<<v[i]; 32 } 33 return 0; 34 }
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/p/5332011.html，如需转载请自行联系原作者
