洛谷P1012 拼数
题目大意
给定 nn个正整数，将它们拼接成一排，使得拼接得到的整数最大。
数据范围： 1≤n≤20，1≤ai≤1e9。
分析
直接按数值大小降序排列不一定得到最大结果，例如 13 和 312：13 < 312，但拼接成 13312 和 31213，后者更大。
正确的比较方式是比较两个数 xx 和 yy 的拼接结果：如果 x+y>y+x（这里的加号表示字符串拼接），则 x 应该排在 y前面。
为什么呢？我们联想一下普通的数字排序，因为有明显的比较规则，所有我们用sort可以轻松排序，这里也是一样的，通过知道了排序规则后，就可以用sort（把sort理解成一个两两比较无数次，使得得到想要的排序顺序即可）。
Solution
标签： 贪心，排序
算法思路
- 将所有整数转换为字符串。
- 定义比较函数 comp(a, b)：返回 a + b > b + a，即若 a 接在 b 前面得到的字符串更大，则 a 应排在 b 前面。
- 按此比较规则对字符串数组进行降序排序。
- 将排序后的字符串依次拼接，输出结果。
代码说明
使用 sort 配合自定义比较函数，时间复杂度 O(L*nlogn)，其中 L 为字符串平均长度（最大 10），完全可行。
注意比较函数直接返回布尔值，符合 sort 的预期。
拼接结果直接用 cout 输出字符串，无需处理前导零（因为输入为正整数）。
时间复杂度
排序 O(nlogn⋅L)，n≤20n≤20 时极快。
空间复杂度 O(n⋅L)。
下面是代码
#include<bits/stdc++.h>
using namespace std;
using db = long double;
using ll = long long;
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0);
#define pll pair<ll,ll>
const ll N = 1e5 + 5;
const ll mod = 998244353;
const ll inf = LLONG_MAX;bool comp(string a, string b){return a + b > b + a;
}
void solve(){ll n; cin >> n;vector<string> aa;for(ll i = 1; i <= n; i++){string s1; cin >> s1;aa.push_back(s1);}sort(aa.begin(),aa.end(),comp);for(string a : aa){cout<<a;}cout<<endl;
}int main(){fast;ll t = 1; //cin >> t;while(t--){solve();}
}