题目

Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given { 32, 321, 3214, 0229, 87 }, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.

Input Specification:
Each input file contains one test case. Each case gives a positive integer $N (≤10^4)$N(≤104) followed by N number segments. Each segment contains a non-negative integer of no more than 8 digits. All the numbers in a line are separated by a space.

Output Specification:
For each test case, print the smallest number in one line. Notice that the first digit must not be zero.

Sample Input:

5 32 321 3214 0229 87

Sample Output:

22932132143287

解题思路

　　题目大意： 给N个数字，然后组合成一个数字，求最小的组合。
　　解题思路： 这道题的关键在于，抽象出题目要求的排序规则，使用sort函数进行排序。我们不妨从Demo中总结一下——
　　显然，小的要放前面，0229比3214要小，比更短的87也更小，比其他都要小，所以放最前面。这一点符合string的operator<规则，可以直接使用a<b。
　　但是麻烦的是， 并不是所有的字符串都符合这个规则，其中，3214比32要大，但是如果把3214放在32前面，显然不是正确的选择——
　
　　但如果 （a+b）<（b+a）的组合成立的话 ，我们发现，这几乎符合所有的条件，我们可以得到最小的排序组合。根据sort的排序规则，如果符合规则（a+b）<（b+a），那么a和b保持原来的顺序，否则交换顺序。
　　此外，测试数据存在边界情况，第二个测试点，最大的数据可能是0，此时要输出0。

/*
** @Brief:No.1038 of PAT advanced level.
** @Author:Jason.Lee
** @Date:2018-12-16
** @status: Accepted!
*/
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<sstream>
using namespace std;
int main(){
	int N;
	while(cin>>N){
		vector<string> segments;
		string temp;
		for(int i=0;i<N;i++){
			cin>>temp;
			segments.push_back(temp);
		}
		// 使用lambda表达式比定义cmp函数更简洁
		sort(segments.begin(),segments.end(),[](string a,string b){return (a+b)<(b+a);});
		// 使用stringstream可以轻易的把string转换成int型，
		//易于判断string是否是零，以及消除首部多余的0
		stringstream strNum;
		int number;
		strNum<<segments[N-1];
		strNum>>number;
		if(number==0){
			cout<<0<<endl;
			continue;
		}
		strNum.clear();
		strNum<<segments[0];
		strNum>>number;
		cout<<number;
		for(int i=1;i<N;i++){
			cout<<segments[i];
		}
		cout<<endl;
	}
	
	return 0;
} 

总结

　　这道题有一种大道至简、返璞归真的感觉，最开始总结规律，搞得很复杂，把排序规则写的很冗余，但是还是通过了，后来参考了别人的代码，发现原来可以如此简洁，看来总结抽象的能力还是不够。发现了规律了之后，其实并不难。