1038. Recover the Smallest Number (30)

时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue

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

---

提交代码

 

 

学习网址：http://blog.csdn.net/sinat_29278271/article/details/48047877

里面的传递性是可以证明的

 

1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<queue> 6 #include<vector> 7 #include<cmath> 8 #include<string> 9 using namespace std; 10 vector<string> v; 11 bool cmp(string a,string b){ 12 return a+b<b+a; 13 } 14 int main(){ 15 //freopen("D:\\INPUT.txt","r",stdin); 16 int n,i; 17 scanf("%d",&n); 18 string s; 19 for(i=0;i<n;i++){ 20 cin>>s; 21 v.push_back(s); 22 } 23 sort(v.begin(),v.end(),cmp); 24 s=""; 25 for(i=0;i<n;i++){ 26 s=s+v[i]; 27 } 28 for(i=0;i<s.length();i++){ 29 if(s[i]!='0'){ 30 break; 31 } 32 } 33 34 if(i==s.length()){ 35 printf("0\n"); 36 } 37 else{ 38 for(;i<s.length();i++){ 39 cout<<s[i]; 40 } 41 cout<<endl; 42 } 43 return 0; 44 }

 

转载于:https://www.cnblogs.com/Deribs4/p/4770206.html

总结

以上是生活随笔为你收集整理的pat1038. Recover the Smallest Number (30)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。