洛谷千题详解 | P1012 [NOIP1998 提高组] 拼数【C++、Java语言】

博主主页：Yu·仙笙

 

专栏地址：洛谷千题详解

目录

题目描述

输入格式

输出格式

输入输出样例

解析：

C++源码：

C++源码2：

C++源码3：

Java源码：

---

-------------------------------------------------------------------------------------------------------------------------------  

-------------------------------------------------------------------------------------------------------------------------------  

题目描述

设有 n 个正整数 a1​…an​，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

-------------------------------------------------------------------------------------------------------------------------------  

输入格式

第一行有一个整数，表示数字个数 n。

第二行有 n 个整数，表示给出的 n 个整数ai​。

-------------------------------------------------------------------------------------------------------------------------------  

输出格式

一个正整数，表示最大的整数

-------------------------------------------------------------------------------------------------------------------------------  

输入输出样例

输入 #1复制

3
13 312 343

输出 #1复制

34331213

输入 #2复制

4
7 13 4 246

输出 #2复制

7424613

-------------------------------------------------------------------------------------------------------------------------------  

解析：

思路分析

数字收尾相接可以认为是字符串相加，故题意为有 nn 个字符串，s1​,s2​,…sn​，首尾相接形成了一个新字符串，求新字符串字典序最大值。

做法：

搜索（部分分） 暴力全排列搜索所有字符串的顺序，比较大小，得出最终答案。

贪心（满分）

对贪心正确性的证明：
分析可见两同样长字符串 s1​,s2​，若s1​ 比s2​ 大，必有 x 使得s1​ 在 x 位第一次比s2​ 大 。

说明只要前面的位大，就可以忽略后面的位，可以使用贪心解决，把对字典序贡献最大的放在前面。比较方法只要比较s1​+s2​ 和s2​+s1​ 的大小即可。

如：2 和 19，比较 2 和 19 哪个放在前面使字典序最大，也就是即比较 219 和 192 哪个大，因为 219 比 192 大，所以把 2 放在 19 前面

使用比较函数 cmp 后 sort 将字符串输出可得答案

-------------------------------------------------------------------------------------------------------------------------------  

C++源码：

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

-------------------------------------------------------------------------------------------------------------------------------  

C++源码2：

#include 
using namespace std;
const int N = 25;
string a[N], ans;
bool vis[N];
int n, f;
void dfs(int depth, string now) {
	if (depth == n) {
		ans = max(ans, now), f = 1;
		return;
	}
	if (f && now < ans && now != ans.substr(0, now.size())) return;
	for (int i = 1; i <= n; i ++)
		if (!vis[i]) {
			vis[i] = true;
			dfs(depth + 1, now + a[i]);
			vis[i] = false;
		}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	sort(a + 1, a + 1 + n, greater());
	dfs(0, "");
	cout << ans << '\n';
	return 0;
}

-------------------------------------------------------------------------------------------------------------------------------  

C++源码3：

#include 
#define int long long
using namespace std;
int n,m;
string a, b;
int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
void write(int n){
    if(n==0) return;
    write(n/10);
    putchar(n%10+'0');
}
signed main(){
    cin >> a >> b;
    cout << a + b;
    return 0;
}

-------------------------------------------------------------------------------------------------------------------------------  

Java源码：

import java.util.Scanner;
 
public class P1012NOIP1998提高组拼数 {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		String s[]=new String[n];
		for (int i=0;i
		for (int i=0;i
			for (int j=i+1;j
				/*
				 * 为解决s[i]=321,s[j]=32时
				 *32132>32321的情况
				 */
				String s1=s[i]+s[j];	
				String s2=s[j]+s[i];
				if (Integer.parseInt(s2)>Integer.parseInt(s1)) {
					String temp=s[i];
					s[i]=s[j];
					s[j]=temp;
				}
			}
		}
		for (int i=0;i
	}
}

-------------------------------------------------------------------------------------------------------------------------------