拼数问题

2014年10月20日3,7780

来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1436

题目描述

设有n个正整数，请将它们拼接成一排，组成一个最大的多位整数。例如：n=3时，3个整数13，312，343拼接成的最大整数为：34331213。

输入

第一行为正整数个数n（n<=10），接下来n行，每行一个正整数（integer类型）。

输出

能拼成的最大整数

样例输入

3 13 312 343

样例输出

34331213

代码

爆搜

#include<iostream>
using namespace std;
int n;
string ans,now;
string str[11];
bool used[11];
void search(int k)
{
	if(k==n){if(now>ans)ans=now;return;}
	for(int i=1;i<=n;i++)
		if(!used[i])
		{
			string temp=now;
			now+=str[i];
			used[i]=1;
			search(k+1);
			used[i]=0;
			now=temp;
		}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>str[i];
    search(0);
    cout<<ans;
	return 0;
}

#include<iostream>

using namespace std;

int n;

string ans,now;

string str[11];

bool used[11];

void search(int k)

{

if(k==n){if(now>ans)ans=now;return;}

for(int i=1;i<=n;i++)

if(!used[i])

{

string temp=now;

now+=str[i];

used[i]=1;

search(k+1);

used[i]=0;

now=temp;

}

int main()

{

cin>>n;

for(int i=1;i<=n;i++)

cin>>str[i];

search(0);

cout<<ans;

return 0;

}

今天学弟在做这题

。。。然后看了一眼发现我以前是爆搜，实际上正解是贪心吧，某次模拟赛有出过类似的，排序后输出

字典序倒序是有反例的

#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int n;
string a[15];
bool cmp(string a,string b)
{
	return a+b>b+a;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
		cout<<a[i];
	return 0;
}

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

int n;

string a[15];

bool cmp(string a,string b)

{

return a+b>b+a;

}

int main()

{

cin>>n;

for(int i=1;i<=n;i++)

cin>>a[i];

sort(a+1,a+n+1,cmp);

for(int i=1;i<=n;i++)

cout<<a[i];

return 0;

}

« 「BZOJ2079」[POI2010] Guilds 「BZOJ1110」[POI2007] 砝码Odw »

hzwer.com _ Home | http://hzwer.com

拼数问题

题目描述

输入

输出

样例输入

样例输出

代码

分类目录

热门文章

Myfriends

近期评论