1038 Recover the Smallest Number

最新推荐文章于 2022-08-19 05:48:02 发布

ChenyutingZJU

最新推荐文章于 2022-08-19 05:48:02 发布

阅读量185

点赞数

分类专栏： PAT甲级

本文链接：https://blog.csdn.net/chenyutingdaima/article/details/82014727

版权

PAT甲级专栏收录该内容

54 篇文章

订阅专栏

本文介绍了一种算法，用于从给定的数字段集合中构造出最小的可能数字。通过字符串排序和零前缀移除的方法，确保了组合出的数字为最小值。示例输入包含多个数字段，通过特定的排序规则，输出最小可能的数字。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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 (≤10
4
) 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

解题思路：
1.以字符串的方式读入，关键是用到string的排序方法。
2.将读入拼接到一起后，删除前面的零。
3.当全部删除与以后要特判输出0。

#include<cstdio> 
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=1e4+10;
string str[maxn];
bool cmp(string a,string b){
    return a+b<b+a;
}

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