P1012 [NOIP 1998 提高组] 拼数题解

【NOIP1998提高组】拼数 题解

题目描述

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

输入格式

• 第一行：数字个数 n
• 第二行：n 个整数

输出格式

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

---

解题思路

问题难点

这道题看起来简单，但其实暗藏玄机。如果直接按数字大小降序排列，会出现问题：

举个栗子：

• 数字：32 和 321
• 按数值排序：32 > 321
• 拼接结果：32321
• 但正确答案应该是：32132

核心思想

不能单纯比较数字大小，而应该比较两种拼接方式的结果！

---

算法设计

关键技巧

1. 将数字转为字符串 - 方便拼接和比较
2. 自定义排序规则 - 比较 a+b 和 b+a 的大小
3. 贪心思想 - 每次选择能使结果最大的拼接方式

比较规则详解

cpp
// 对于两个字符串a和b
// 如果 a+b > b+a，则a应该排在b前面
// 否则b排在a前面

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