51Nod 1097 拼成最小的数

Problem

设有n个正整数，将它们联接成一排，组成一个最小的多位整数。

例如： n=2时，2个整数32，321连接成的最小整数为：32132， n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

Solution

最优的情况字符串a+b<b+a，排序即可。

设置num(x)为字符串x代表的数字，num(a)10^|b|+num(b) < num(b)10^|a|+num(a) -> num(a)/(10^|a|-1) < num(b)/(10^|b|-1)，排序即可。

Code1

#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
string s[10020];
int n;
int cmp(string x,string y){
	return x+y<y+x;
}
int main(){
	io_opt;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	sort(s+1,s+1+n,cmp);
	string ans="";
	for(int i=1;i<=n;i++){
		ans+=s[i];
	}
	for(int i=0;i<ans.size();i++){
		if(i!=0&&i%1000==0) cout<<endl;
		cout<<ans[i];
	}
	return 0;
}

Code2

#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long double ld;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
struct E{
	int x,len;
}e[10020];
int n;
int t[20]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
int cmp(E x,E y){
	return (ld)x.x/(t[x.len]-1)<(ld)y.x/(t[y.len]-1);
}
int cur=0,tmp[20];
int main(){
	io_opt;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>e[i].x;
		e[i].len=0;
		int xx=e[i].x;
		while(xx){
			e[i].len++;
			xx/=10;
		}
	}
	sort(e+1,e+1+n,cmp);
	int cnt=0;
	for(int i=1;i<=n;i++){
		cur=0;
		while(e[i].x){
			tmp[++cur]=e[i].x%10;
			e[i].x/=10;
		}
		for(int j=cur;j>=1;j--){
			cout<<tmp[j];
			cnt++;
			if(cnt%1000==0){
				cout<<endl;
			}
		}
	}
	return 0;
}