前言
首先,我们最初的想法一定是输入字符串,然后对字符串进行排序,最后依次输出,于是你获得 $75$ 分。
给出一组自编 hack 数据:
2
379 3791
如果按刚才的思路输出应该是:
3791379
可是正确输出应该是:
3793791
题目解法
可以看出,即使完全相同的两个字符串,拼凑的方式不同,结果也不同。
假设两个字符串:
- a = 123
- b = 456
我们定义加法为拼接,那么:
- a + b = 123456
- b + a = 456123
很容易看出 $a+b<b+a$,也能看出当两个字符串 $a,b$ 比大小时,如果 $a+b>b+a$ 说明 $a$ 大,否则说明 $b$ 大(或相等,这里相等的情况算谁大都无所谓)。
所以我们的 cmp
函数需要这么写:
bool cmp(string a,string b)
{return a+b>b+a;
}
最后,从头到尾输出排序好的字符串就结束了。
代码
代码不加注释了,应该能看得懂。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool cmp(string a,string b)
{return a+b>b+a;
}
int main()
{ios::sync_with_stdio(false);//快速输入int n;string s[21];cin>>n;for(int i=0;i<n;i++){cin>>s[i];}sort(s,s+n,cmp);for(int i=0;i<n;i++){cout<<s[i];}return 0;
}