Pat(Advanced Level)Practice--1038(Recover the Smallest Number)

Pat1038代碼

題目描述：

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
      

AC代碼：

如果一個字元串是另一個字元串的字首，那麼兩個字元串的大小要分情況而定

例如：S1=32

            S2=32XXXXX

那麼隻要比較3232XXXXX

                        32XXXXX32之間的大小即可

兩個循環就可以搞定。

解法一，逐個字元進行比較，比較繁瑣，但效率很高

解法二，是在解法一的基礎上改進的，既然要求兩個字元串的大小

那麼直接進行相加比較豈不是更快。（這是在解法一快寫完時才發現的捷徑）

解法一：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

bool cmp(const string &s1,const string &s2)
{
	int i,j;
	for(i=0,j=0;i<s1.size()&&j<s2.size();i++,j++)
	{
		if(s1[i]==s2[j])
			continue;
		else
			break;
	}
	if(i==s1.size())//s1是s2的字首
	{
		int k,m;
		for(k=0;k<s2.size()&&j<s2.size();k++,j++)
		{
			if(s2[j]==s2[k])
				continue;
			else if(s2[k]<s2[j])
				return true;
			else 
				return false;
		}
		for(m=0;m<s1.size()&&k<s2.size();m++,k++)
		{
			if(s1[m]==s2[k])
				continue;
			else if(s2[k]<s1[m])
				return true;
			else 
				return false;
		}
		return true;
	}
	else if(j==s2.size())//s2是s1的字首
	{
		int k,m;
		for(k=0;k<s1.size()&&i<s1.size();i++,k++)
		{
			if(s1[k]==s1[i])
				continue;
			else if(s1[i]<s1[k])
				return true;
			else 
				return false;
		}
		for(m=0;m<s2.size()&&k<s1.size();m++,k++)
		{
			if(s2[m]==s1[k])
				continue;
			else if(s2[m]<s1[k])
				return true;
			else
				return false;
		}
		return true;
	}
	else 
	{
		if(s1<s2)
			return true;
		else 
			return false;
	}
}

int main(int argc,char *argv[])
{
	int i,j,n;
	string s;
	vector<string> v;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		cin>>s;
		v.push_back(s);
	}
	sort(v.begin(),v.end(),cmp);
	string ans=v[0];
	for(i=1;i<n;i++)
		ans+=v[i];
	int t=0;
	while(t<ans.size()&&ans[t]=='0')
		t++;
	if(t==ans.size())
		cout<<"0"<<endl;
	else
		cout<<&ans[t]<<endl;

	return 0;
}
           

解法二：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

bool cmp(const string &s1,const string &s2)
{
	string s3,s4;
	s3=s1+s2;
	s4=s2+s1;
	if(s3<s4)
		return true;
	else 
		return false;
}

int main(int argc,char *argv[])
{
	int i,j,n;
	string s;
	vector<string> v;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		cin>>s;
		v.push_back(s);
	}
	sort(v.begin(),v.end(),cmp);
	string ans=v[0];
	for(i=1;i<n;i++)
		ans+=v[i];
	int t=0;
	while(t<ans.size()&&ans[t]=='0')
		t++;
	if(t==ans.size())
		cout<<"0"<<endl;
	else
		cout<<&ans[t]<<endl;

	return 0;
}
           

本題核心是貪心算法，關鍵是排序算法怎麼寫的問題。。。