PAT A1038 Recover the Smallest Number (30分)

前言

传送门

正文

参考题解

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
/*
给定n个数字，每个数字位数不超过8位，现在需要将这n个数字按照某个顺序排列起来，
使得排列后形成的新的数字的值是最小的，并输出这个最小的数字。 

贪心策略：
对于字符串s1和s2，若时s1+s2<s2+s1，则把s1放在s2的前面，否则s2放在s1的前面 
注意点：
1、结果串的所有前导0都要去掉，如果去掉后，结果的长度为0，则输出"0"
2、涉及到拼接，故使用字符串来进行数据的存储,同时注意前导0的去除（利用substr） 
*/
const int N=1e4+10;
string str[N],res;
int n; 
bool cmp(string a,string b){
	return a+b<b+a;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)cin>>str[i];
	sort(str,str+n,cmp);
	for(int i=0;i<n;i++)res+=str[i];
	int len=res.size(),i=0; 
	/*去除前导0两种方式*/
	//while(i<len&&res[i]=='0') i++;
	//if(i==len)cout<<"0"<<endl;
	//else cout<<res.substr(i)<<endl;
	
	while(res.size()!=0&&res[0]=='0')res.erase(res.begin()); 
	if(res.size()==0)cout<<"0"<<endl;
	else cout<<res<<endl;

	return 0;
}