原题链接:https://www.luogu.com.cn/problem/P1012
题意解读:通过某种合理的排序方式,使得排序后的数字连在一起最大。
解题思路:
此题关键在于排序,对于两个数字,哪个数字应该排在前面呢?
1、思考误区
很容易想到,给定两个数abcd、xyz,先比较第一位a和x,谁大谁排前面,一直到c和z。
再来看d,这里就没有确定的排序策略了,
举例:
234、2340,显然234应该排在前面;
234、2341,则234应该排在前面;
234、2343,则2343应该排在前面;
。。。
策略不固定,处理很容易有遗漏造成失分。
2、正确思路
要比较abcd,xyz两个数哪个数排在前面,
根据题意,只需要比较abcdxyz,xyzabcd哪个大,
如果abcdxyz大,则abcd排在前面。
为了方便做数字连接和大数的比较,用string表示数字即可。
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
string s[N];
bool cmp(string s1, string s2)
{
return s1 + s2 > s2 + s1;
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> s[i];
sort(s + 1, s + n + 1, cmp);
for(int i = 1; i <= n; i++) cout << s[i];
}
标签:string,拼数,前面,int,洛谷题,s1,P1012,234,排序 From: https://www.cnblogs.com/jcwy/p/17997325