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 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 #include2 #include 3 #include 4 #include 5 using namespace std; 6 //排序问题 7 int N; 8 vector v, temp; 9 string res = "", str = "";10 void permuteDFS(int u,vector &visit)//使用DFS11 {12 if (u == v.size())13 {14 for (auto a : temp)15 str += a;16 res = res > str ? str : res;17 str = "";18 return;19 }20 for (int i = 0; i < N; ++i)21 {22 if (visit[i] == true)continue;23 visit[i] = true;24 temp.push_back(v[i]);25 permuteDFS(i + 1, visit);26 temp.pop_back();27 visit[i] = false;28 }29 }30 31 void permutex(int u)//使用递归32 {33 if (u == v.size())34 {35 for (auto a : v)36 str += a;37 res = res > str ? str : res;38 str = "";39 }40 for (int i = u; i < N; ++i)41 {42 swap(v[i], v[u]);43 permutex(i + 1);44 swap(v[i], v[u]);45 }46 }47 48 void Sort()//使用排序法则49 {50 sort(v.begin(), v.end(), [](string a, string b) { return a + b < b + a; });51 res = "";52 for (auto a : v)53 res += a;54 }55 56 int main()57 {58 cin >> N;59 v.resize(N);60 vector visit(N, false);61 for (int i = 0; i < N; ++i)62 {63 cin >> v[i];64 res += v[i];65 }66 //permutex(0);67 //permuteDFS(0, visit);68 Sort();69 while (!res.empty() && res[0] == '0')70 res.erase(0, 1);71 if (res.size() == 0)cout << 0;72 cout << res << endl;73 return 0;74 }