【题解】ACOJ12103数字连接

题面传送门

解法:

看到连接字符串,第一反应肯定是比较它们的字典序
假设我们只比较字典序,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<string> s;
int main()
{
string t;
int n,flag = 0;
cin >> n;
for(int i = 0;i < n;i ++) {
cin >> t;
s.push_back(t);
}
sort(s.begin(), s.end());
for(int i = n - 1;i >= 0;i --) {
// 注意,这里需要倒着输出
cout << s[i];
}
return 0;
}

然而,你只能得到$20pts$。为什么?考虑这种输入:

2
5 50

请问最好的排法应该是什么?显然是550,而你的程序跑的是505

为什么?问题出现在了两个字符串不一样长

如何使他们一样长?下面的代码将会展示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<string> s;
bool cmp(string a,string b){
if(a.length() == b.length()) return a < b;
else if(a.length() != b.length()){
string c = a+b,d = b+a;
return c < d;
}
}
int main()
{
string t;
int n,flag = 0;
cin >> n;
for(int i = 0;i < n;i ++) {
cin >> t;
s.push_back(t);
}
sort(s.begin(), s.end(),cmp);
for(int i = n - 1;i >= 0;i --) {
cout << s[i];
}
return 0;
}

我们使用了cmp函数,如果两个字符串长度不相等,那么把他们的两种组合排列出来,看看哪个排列的字典序大