PAT_A1038#Recover the Smallest Number

Source:

PAT A1038?Recover the Smallest Number?(30?分)

Description:

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?(≤) followed by?Nnumber 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

Keys:

• 贪心

Code:

 1 /*
 2 Data: 2019-07-23 18:47:04
 3 Problem: PAT_A1038#Recover the Smallest Number
 4 AC: 16:22
 5 
 6 题目大意：
 7 给几个数，求拼成的最小数
 8 */
 9 #include<cstdio>
10 #include<string>
11 #include<iostream>
12 #include<algorithm>
13 using namespace std;
14 const int M=1e4+10;
15 string s[M];
16 
17 bool cmp(string a,string b)
18 {
19     return a+b < b+a;
20 }
21 
22 int main()
23 {
24 #ifdef    ONLINE_JUDGE
25 #else
26     freopen("Test.txt","r",stdin);
27 #endif
28 
29     int n;
30     scanf("%d",&n);
31     for(int i=0; i<n; i++)
32         cin >> s[i];
33     sort(s,s+n,cmp);
34     string ans="";
35     for(int i=0; i<n; i++)
36         ans += s[i];
37     while(ans.size()>1 && ans[0]==‘0‘)
38         ans.erase(0,1);
39     cout << ans;
40 
41     return 0;
42 }