PAT 1038 Recover the Smallest Number (30 分)

以你之姓@ 2024-02-19 21:55 18阅读 0赞

## 1038 Recover the Smallest Number (30 分) ##

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 (≤104) 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

这个比较很重要，妙！

`s1+s2拼接起来比s2+s1拼接起来小的时候，s1应该排在s2的前面`

int cmp(string a,string b)
    {
    	return a+b<b+a?1:0;
    }

#include<iostream>
    #include<vector>
    #include<cstring> 
    #include<algorithm>
    using namespace std;
    int cmp(string a,string b)
    {
    	return a+b<b+a?1:0;
    }
    int main()
    {
    	vector<string> a;
    	string s;
    	int n,i,j,t,flag=0;
    	cin>>n;
    	for(i=0;i<n;i++)
    	{
    		cin>>s;
    		a.push_back(s);
    	}
    	sort(a.begin(),a.end(),cmp);
    	for(i=0;i<n;i++)
    	{
    		for(j=0;j<a[i].size();j++)
    		if(!flag)
    		{
    			if(a[i][j]!='0')
    			{
    				cout<<a[i][j];
    				flag=1;
    			}
    		}
    		else
    		{
    			cout<<a[i][j];
    		}
    	}
    	if(flag==0)
    	cout<<0<<endl;
    	return 0;
    }