PAT-1038 Recover the Smallest Number

Recover the Smallest Number

Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given { 32, 321, 3214, 0229, 87 }, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.

Input Specification

Each input file contains one test case. Each case gives a positive integer N (≤10​^4​​) followed by N number segments. Each segment contains a non-negative integer of no more than 8 digits. All the numbers in a line are separated by a space.

Output Specification

For each test case, print the smallest number in one line. Notice that the first digit must not be zero.

Sample Input

5 32 321 3214 0229 87

Sample Output

22932132143287

---

这道题以前就没做对，这次也没做对，记录一下。

两次读完题的反应完全一致：谁“小”把谁排前面。

1. 若两个数位数相同，按数值比较
2. 若两个数位数不同，位数少的数字补0至位数相同，按数值比较。

我的cmp是这么写的

bool cmp(string a, string b)
{
	string p1 = a, p2 = b;
	int diff = p1.size() - p2.size();
	if (diff < 0) swap(p1, p2);
	for (int i = 0; i < abs(diff); i++) p2.push_back('0');
	return p1 < p2;
}

Debug模式在运行时报错，Assert failed: Invalid comparor. 根据cppreference，comparer需满足

• 反自反.对于所有的a,comp(a,a)==false
• 反对称.若comp(a,b)==true，则comp(b,a)==false
• 传递 若comp(a,b)==true，comp(b,c)==true,则comp(a,c)==true.

我们的comparer违背了反对称性。comp(9,10)===comp(10,9)

查到string的<操作符按照字典序进行比较。而我们辛辛苦苦的补0，就是要按字典序比较。

事实证明字典序也不对。考虑32和321，按照字典序，32<321，但这样拼接的32321却比32132要大。似乎还要考虑字符串的首位和末位。

查了别人的代码，最好的解决办法是，把问题原样丢给C++

bool cmp(string s1, string s2)
{
	return s1 + s2 > s2 + s1;
}

我居然还想了半天，整个人都不好了😶

#include "string"
#include "vector"
#include "iostream"
#include "algorithm"
using namespace std;
bool cmp(string s1, string s2)
{
	//sort by lexicographical order doesn't work here. 33<321,but 33321 > 32133. :-(
	//but we can throw the problem at cpp :-)
	auto p1 = s1;
	auto p2 = s2;
	return p1+p2 < p2+p1;
}
int main()
{
	int n;
	cin >> n;
	vector<string> v=vector<string>(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	sort(v.begin(), v.end(), cmp);
	string res;
	for (auto i : v) res.append(i);
	int i = 0; while (res[i] == '0') i++;
	res = res.substr(i);
	if (res.size() == 0) res = "0";
	cout << res << endl;
	return 0;
}