PAT(贪心)——1038. Recover the Smallest Number (30)

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 (<=10000) 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. Do not output leading zeros.

Sample Input:
5 32 321 3214 0229 87
Sample Output:
22932132143287

题目大意：

给一堆数字组成的字符串，把他们按一定顺序排列，使组成的数字最小。

题目解析：

思路完全借鉴自柳神，https://www.liuchuo.net/archives/2303。
关键代码：

bool cmp(string a,string b){
	return a+b<b+a;
}

具体代码：

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(string a,string b){
	return a+b<b+a;
}
int main()
{
    int n;
    string s[10005];
    cin>>n;
    for(int i=0;i<n;i++)
    	cin>>s[i];
    sort(s,s+n,cmp);
    
    string res="";
    bool flag=true;
    for(int i=0;i<n;i++)
    	res+=s[i];
    for(int i=0;i<res.size();i++){
    	if(flag&&res[i]=='0')
    		continue;
    	flag=false;
    	printf("%c",res[i]);
	}
	if(flag)
		printf("0");
    return 0;
}