【练习】拼数
拼数
https://ac.nowcoder.com/acm/problem/16783
题目
题目描述：设有n个正整数（n ≤ 20），将它们联接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213
又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613
输入描述：
第一行，一个正整数n。
第二行，n个正整数。
一个正整数，表示最大的整数
解析
首先我们来看一下题目：
- 题目要我们把一堆数字字符串拼成一个最大的数。
这道题也是贪心：
- 这道题为什么符合贪心呢？因为只要部分的顺序在整体中依旧成立：
- 也就是如果两个串：串A和串B进行比较。这个时候串A在前比串B在前要大，那么在整个串中，也符合这个规律。
贪心策略：
- 我们上面有一句话说的好，就是把串A和串B进行比较，判断怎么大就怎么排。
- 那怎么判断呢？其实很简单，我们的string类里面是重载了运算符的，用比大小就可以了！当然是连起来以后比大小。
- 也就是说，只要连起来以后，怎么大，就怎么放（好了，我们的排序方法就这么简单的出来了）。
咋操作：
- 我们这里用一个cmp重载string的运算符，再用sort排序就好啦。
打代码咯：
- 先输入我们所有的字符串。
- 然后用重载运算符后的sort排个序。
- 连起来输出就好了。
AC代码
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MAX = 27;
string s[MAX];
//全局变量区
bool cmp(const string& u, const string& v) {
return u + v > v + u;
}
//函数预定义区
int main() {
IOS;
int n; 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];
cout << ans << endl;
return 0;
}
//函数区牛客算法竞赛入门课题解 文章被收录于专栏
憨憨的专栏
投递哔哩哔哩等公司6个岗位