PAT-ADVANCED1038——Recover the Smallest Number

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805449625288704

题目描述：

题目翻译：

1038 复原出最小的数字

给定一组数字段，你需要从它们中恢复最小的数字。例如，给定{32,321,3214,0229,87}，我们可以恢复许多数字，例如32-321-3214-0229-87或0229-32-87-321-3214，关于不同的组合顺序这些段，最小的数字是0229-321-3214-32-87。

输入格式：

每个输入文件包含一个测试用例。每个测试用例给出一个正整数N(<= 10 ^ 4)，紧跟着N个数字段。每个片段包含一个不超过8位的非负整数。一行中的所有数字由一个空格分隔。

输出格式：

对每个测试用例，在一行中输出最小的数字。注意数字首位不能是0。

输入样例：

5 32 321 3214 0229 87

输出样例：

22932132143287

知识点：贪心算法

思路：贪心算法

总策略是：对数字串S1和S2，如果S1 + S2 < S2 + S1，那么把S1放在S2的前面；否则，把S2放在S1的前面。

最后的结果中需要把所有的前导零都去除。但也要注意，如果去除前导零后结果的长度变为0，说明结果串应为0，则输出“0”。

时间复杂度是O(NlogN)。空间复杂度是O(N)。

C++代码：

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

bool cmp(string s1, string s2);

int main(){
	int N;
	scanf("%d", &N);
	string input[N];
	for(int i = 0; i < N; i++){
		cin >> input[i];
	}
	sort(input, input + N, cmp);
	string result;
	for(int i = 0; i < N; i++){
		result += input[i];
	}
	while(result.size() != 0 && result[0] == '0'){
		result.erase(result.begin());
	}
	if(result.size() == 0){
		printf("0\n");
	}else{
		cout << result << endl;
	}
	return 0;
}

bool cmp(string s1, string s2){
	return (s1 + s2).compare(s2 + s1) < 0;
}

C++解题报告：

PAT-ADVANCED1038——Recover the Smallest Number

PAT-ADVANCED1038——Recover the Smallest Number

思路：贪心算法

相关推荐