# PAT 解题报告 1038. Recover the Smallest Number (30)

### 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.

### 1038. Recover the Smallest Number 算法分析：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>

#define REP(i,n) for(int i=0;i<(n);++i)

using namespace std;

int N;
vector<string> segs;

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

void gao(void) {
sort(segs.begin(), segs.end(), cmp2);
string res("");
REP(i, N) res += segs[i];
int ix = 0;
while('0' == res[ix]) ix++;
if(res.substr(ix).size())
cout<<res.substr(ix)<<endl;
else
cout<<0<<endl;
return ;
}

int main(void) {
cin>>N;
segs.resize(N);
REP(i, N) cin>>segs[i];
gao();
return 0;
}

### 1038. Recover the Smallest Number 注意点：

Written on December 29, 2013