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

本文主要是介绍PAT (Advanced Level) Practice 1038 Recover the Smallest Number (30 分) 凌宸1642，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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
 			
*/ 

这篇关于PAT (Advanced Level) Practice 1038 Recover the Smallest Number (30 分) 凌宸1642的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！