【PAT甲级 - C++题解】1038 Recover the Smallest Number

简介: 【PAT甲级 - C++题解】1038 Recover the Smallest Number

1038 Recover the Smallest Number


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 (≤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 个数字,他们可以随意进行组合成不同的数字,例如 {32,321,3214,0229,87} 可以组成 32-321-3214-0229-87 或 0229-32-87-321-3214 等,但所有组合中 0229-321-3214-32-87 得到的数字是最小的。


现在我们需要找到这 N 个数字组合后最小的那个数字。


思路

这题我们可以发现一个规律,可以通过判断拼接后的字符串的大小来进行排序,假定有字符串 x 和 y :


如果 x+y > y+x ,则 x “大于” y ,即 x 排在 y 的后面。

如果 x+y < y+x ,则 x “小于” y ,即 x 排在 y 的前面。

注意: 上述的加法运算并不是实际意义上的整数加法运算,而是字符串的拼接。当然,大于小于也不是整数的大小比较,而是指排序的规则。


例如 x = 3 且 y = 32 ,可以发现:


x + y = 332 > y + x = 323 ,所以我们认为 x “大于” y ,即 x 要排在 y 的后面。

故通过上述规则对数组中的所有字符串进行排序,然后再将排序后的数组中的字符串拼接起来得到的字符串一定是最小的。


代码

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
string a[N];
int n;
int main()
{
    //输入每个值
    cin >> n;
    for (int i = 0; i < n; i++)    cin >> a[i];
    //按规则进行排序
    sort(a, a + n, [](string& a, string& b) {return a + b < b + a; });
    //合成字符串
    string res = "";
    for (int i = 0; i < n; i++)    res += a[i];
    //去掉前缀0
    int k = 0;
    while (k + 1 < res.size() && res[k] == '0')   k++;
    //输出结果
    cout << res.substr(k) << endl;
    return 0;
}
目录
相关文章
|
C++
【PAT甲级 - C++题解】1040 Longest Symmetric String
【PAT甲级 - C++题解】1040 Longest Symmetric String
64 0
|
算法 C++
【PAT甲级 - C++题解】1044 Shopping in Mars
【PAT甲级 - C++题解】1044 Shopping in Mars
81 0
|
C++
【PAT甲级 - C++题解】1117 Eddington Number
【PAT甲级 - C++题解】1117 Eddington Number
75 0
|
存储 C++ 容器
【PAT甲级 - C++题解】1057 Stack
【PAT甲级 - C++题解】1057 Stack
73 0
|
存储 C++
【PAT甲级 - C++题解】1055 The World‘s Richest
【PAT甲级 - C++题解】1055 The World‘s Richest
76 0
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
98 1
|
5月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
6月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
42 0
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
38 0
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
93 0
LeetCode 414. Third Maximum Number