1038. Recover the Smallest Number (30)

川长思鸟来 2022-05-31 11:24 114阅读 0赞

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 (<=10000) 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. Do not output leading zeros.

**Sample Input:**

5 32 321 3214 0229 87

**Sample Output:**

22932132143287

--------------------

题目大意：

给定一个数字段集合，你应该从她们中恢复出最小的数字。例如，给定\{32, 321, 3214, 0229, 87\}, 我们可以回复出许多数字例如32-321-3214-0229-87 或 0229-32-87-321-3214 他们的组合顺序不同，最小数字是0229-321-3214-32-87。  
输入规格：  
每个输入文件包含一个测试用例。每个测试用例给出一个正整数N（<=10000），然后是N个字段。每个字段包含不超过8位数的非负整数。直线上得所有数字都用空格隔开。  
输出规范：  
对于每个测试用例，将最小的数字打印在一行中。不要输出首数字0.

代码：

#include<stdio.h>
    #include<algorithm>
    #include<string>
    #include<iostream>
    using namespace std;
    string str[10001],out;
    bool cmp(string a,string b)
    {
        return a+b<b+a;
    }
    int main()
    {
        int i,j,n,m,k,t;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            cin>>str[i];
        }
        sort(str,str+n,cmp);
        for(i=0;i<n;i++)
            out+=str[i];
        for(i=0;i<out.size()&&out[i]=='0';i++);
            if(i==out.size())
            printf("0\n");
            else
            printf("%s\n",out.c_str()+i);
        return 0;
    }