PAT (Advanced Level) Practice 1038 Recover the Smallest Number (30 分) 凌宸1642

题目描述：

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.

译：规定你个一个数字序列集合，，您应该从中恢复最小的数字。 例如，给定 { 32, 321, 3214, 0229, 87 }，我们可以恢复许多数字，例如 32-321-3214-0229-87 或 0229-32-87-321-3214 相对于不同的组合顺序 这些段，最小的数字是 0229-321-3214-32-87。

---

Input Specification (输入说明):

Each input file contains one test case. Each case gives a positive integer N (≤10⁴) 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.

译：每个输入文件包含一个测试用例。 每个 case 给出一个正整数 N (≤10⁴)，后跟 N 个数字段。 每个段包含一个不超过 8 位的非负整数。 一行中的所有数字都用空格分隔。

---

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

---

The Idea：

• 根据题意，其实就是只需要找出满足题意的字符串方式，二而其实题目已经隐含的给出了排序规则，就是组合成最小的数字的顺序，所以可以直接拼接两个字符串，如何拼接最小，即为排序方式。
  • 仅仅是位置不变是不够的，因为可以出现这种情况，在数字序列 1 5 2 4 3中，排序之后的序列为1 2 3 4 5 ，其中数字 1 和4的位置都没有发生变化，但是能够满足题题目意思的枢轴的候选者只有1。这也就产生了作为枢轴候选者的第二个条件：枢轴候选者左边的最大值比枢轴小 (因为题目中说明了 N 个不同的数字)
• 记得去除前导零 。
• 个人见解：题目可能少考虑了一些情况，比如每个数字都有前导 0 的时候，如何抉择？

The Codes:

#include<bits/stdc++.h>
using namespace std ;
bool cmp(string s1 , string s2){
	return s1 + s2 < s2 + s1 ; 
}
int main(){
	int n ;
	cin >> n ;
	vector<string> ss(n) ;
	for(int i = 0 ; i < n ; i ++) cin >> ss[i] ;
	sort(ss.begin() , ss.end() , cmp) ;
	int temp = stoi(ss[0]) ; // 去除第一个数字的前导零 如 0229 --> 229 
	string ans = to_string(temp) ;
	for(int i = 1 ; i < n ; i ++){
		temp = stoi(ss[i]) ;  
		if(temp != 0)ans += ss[i] ; // 答案输出为 0 时，避免输出多个0  
	}
	cout << ans << endl ;
	return 0 ;
}

/*
	PAT 的测试数据中应该不存在类似于下述这种测试数据：
 		
 		in:		3 00 010 001
 			
*/