这是一道经典的字符串题,虽然是以数字样式给出的。
首先,我们来观察只有两个字符串 $a$ 和 $b$ 的情形。因为 $a$ 和 $b$ 的长度可能不相同,根据分析我们可以看出应该这样比较:
$$let\,\,a\,\,be\:\:321\;\;and\;\;b\;\;be\;\;42$$
$$we\;\;have$$
$$a+b=32142<b+a=42321$$
可见正确的比较姿势是把两个字符串续起来再比较。
然后观察有更多的字符串的情形。假设我们有 $n$ 个字符串的集合 $A$,那么 $\exists \; x \in A,\;s.t.\;\forall\;y \in A,\;y\neq x,\;x\geq y$ 。这个 $x$ 应该被放在第一位,因为如果有另一个字符串 $y$ 被放在第一位,那么一定可以在第二从位放 $x$ 且使得 $y+x\leq x+y$,不能满足需求。
综上,我们发现只要用「把两个字符串加进来比较」的方法把字符串排序就好了。如果是直接比较,可能会出错。这个前面的大佬们已经解释并举反例啦!
下面是程序:
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
cin.tie(0);
ios::sync_with_stdio(0);
cin >> n;
string *nums = new string[n], *ed = nums + n;
for (string *i = nums; i != ed; ++i)
cin >> *i;
sort(nums, ed, [](string &a, string &b) { return b + a < a + b; });
for (string *i = nums; i != ed; ++i)
cout << *i;
cout << '\n';
}
偶然回来看到这个,发现自己有五个赞……
有点愧对大家,我贴的这个程序不太好……
一般不建议用裸的 new 和 delete。那段时间我写这样的代码,不好。如果还有后来者看到这份代码,用
vector
代替吧。EOJ 的 Markdown 也太丑了