ZYF036 最大数
大约 3 分钟贪心
ZYF036 最大数
【算法标签】 贪心
【语法标签】 :string、sort、自定义比较函数(cmp)、数组、cin/cout、for循环
给定一组非负整数 ,将这些整数按任意顺序重新排列,每个数不可拆分拼接,使得最终组成的整数最大。
数据范围:,每个整数 。
二、解题思路
数据规模分析
最大到 ,不可能暴搜所有排列( 种)。需要 的排序解决。
此外,数字可能非常大——比如 拼上 ,结果远超 long long 范围,所以必须用字符串 string 存储,不能先算数值再比较。
贪心策略推导
问题的核心是:如何定义两个数的"大小"顺序,使得排序后拼接的结果最大?
先看两个数的情况:给定 和 ,组成的可能就是 ab 和 ba(ab 表示把 和 的字符串拼在一起)。
- 如果
ab>ba,那么 应该排在 前面; - 如果
ab<ba,那么 应该排在 前面。
也就是说,自定义比较规则为:
这个规则是 可传递 的(虽然严谨证明较复杂,但在竞赛中可以放心使用),因此排序后从头到尾拼接就是最大结果。
为什么不能用数值比较?
比如 :
"3"+"30"="330""30"+"3"="303"
显然 "330" > "303",所以 3 应该排在 30 前面。
如果按数值排序(,30 排在前面),拼接得 "303" 反而更小。这说明不能按数值大小排序。
特殊情况:全是 0
如果输入全为 0,比如 ,输入 0 0 0,拼接结果是 "000"。但题目要求的最大整数应该是 "0"。所以需要在排序后特判:如果排序后第一个数就是 "0"(说明最大也是 0,全为 0),直接输出 "0"。
算法流程
- 读入 个数,全部当作字符串读入。
- 用
sort+ 自定义cmp排序:a+b > b+a时 排在 前。 - 特判全 0 情况:排序后第一个字符串为
"0",输出"0"。 - 否则,将所有字符串从头到尾拼接,输出。
手动模拟样例
样例:,输入 10 2。
排序比较:
"10"+"2"="102","2"+"10"="210""210">"102",所以"2"排在"10"前面
排序结果:["2", "10"]
拼接结果:"210",与样例一致。
再试一例:,输入 3 30 34 5 9(经典 LeetCode 179 样例)。
排序后:["9", "5", "34", "3", "30"]
拼接结果:"9534330",正确。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
string a[N]; // 用字符串数组存储
// 自定义比较:a+b > b+a 时 a 排前面
bool cmp(string a, string b) {
return a + b > b + a;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// 按自定义规则排序
sort(a + 1, a + n + 1, cmp);
// 特判:全是 0 的情况
if (a[1] == "0") {
cout << "0" << endl;
return 0;
}
// 拼接输出
for (int i = 1; i <= n; i++) {
cout << a[i];
}
cout << endl;
return 0;
}四、复杂度分析
- 时间复杂度:排序 。每次字符串比较(拼接)开销为字符串长度 ,(因为 最多 10 位数),所以比较可以看作常数。总复杂度 。
- 空间复杂度: 个字符串,每个最长约 10 个字符,总 。
