PAT [1033] Recover the Smallest (25)

发表于 | 分类于

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 

1
5 32 321 3214 0229 87

Sample Output 

1
22932132143287

算法：
排序：本题是要构成的字符串是最小的，还不是字典序最小，所以比较的就是a+b和b+a了。

learing：
1、花式跳过前导零

1
2
while(sum.length() != 0 && sum[0] == '0')
    sum.erase(sum.begin());

1
2
3
int out=0;
for(out=0;out<sum.length()&&sum[out]=='0';out++);
printf("%s",sum.c_str()+out);//char*指针向后移动out个

2、char*=string.c_str();
3、string.length()==0 的话 cout<<string 什么都不会输出！
4、string的length()与size()没区别，源代码是相同的。

code

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<math.h>
using namespace std;

vector<string> v;

bool cmp(const string& a,const string& b)
{
    return a+b<b+a;
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        v.push_back(s);
    }
    
    sort(v.begin(),v.end(),cmp);
    
    string sum="";
    for(int i=0;i<v.size();i++)
        sum+=v[i];
    
    int out=0;  
    for(out=0;out<sum.length()&&sum[out]=='0';out++);//跳过0 
    
    if(out==sum.size())   cout<<0;//要专门输出一次.
    else cout<<sum.c_str()+out;
    
    return 0;
}