PAT 甲级 1038 Recover the Smallest Number 两种思路

本文主要是介绍PAT 甲级 1038 Recover the Smallest Number 两种思路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题的大致思路是每次把能够让拼接后的数字最小的串放在前面，怎么来比较哪个放在前面最小呢？考虑下面两种情况
情况1：321 32 324
情况2：131 13 134
显然应该把第一位最小的放在最前面，第一位相同比较第二位，如果所有位都相同呢？比如上面32和13的情况？可以循环进行比较。比如判断321和32谁放在前面的时候，比较3和3，2和2，3和1得到结果321更小，所以321放在前面。这个循环比较方法的思路和证明并不直观。需要考虑到前n位相同的时候，拼接串需要保证小的数字更早出现。

#include <bits/stdc++.h>
using namespace std;
// 按位循环比较（这个可行性不是那么直观）
bool cmp(const string& a, const string& b)
{int sz = std::max(a.size(), b.size());for (int i = 0; i < sz; ++i) {if (a[i % a.size()] != b[i % b.size()]) {return a[i % a.size()] < b[i % b.size()];}}return true;
}
int main()
{
#ifdef LOCALfreopen("input.txt", "r", stdin);
#endifint n; cin >> n;vector<string> nums(n);for (int i = 0; i < n; ++i) {cin >> nums[i];}sort(nums.begin(), nums.end(), cmp);string ans = "";for (auto& i : nums) ans += i;// 去除前导0bool fro_zero = true;for (auto& i : ans) {if (fro_zero && i != '0') {fro_zero = false;}if (!fro_zero) cout << i;}// 如果全是0，输出0if (fro_zero) cout << 0;cout << endl;
}

另外一种思路更加自然：
考虑a和b两个串，a+b和b+a分别表示a拼接在前面和b拼接在前面。如果a+b<b+a，那么要让拼接的结果更小，只要把a放在前面就可以了。从而可以贪心：在判断a和b谁放在前面的时候，每次都把x+y<y+x的x放在前面。

#include <bits/stdc++.h>
using namespace std;
// 拼接之后比较
bool cmp(const string& a, const string& b)
{return a + b < b + a;
}
int main()
{
#ifdef LOCALfreopen("input.txt", "r", stdin);
#endifint n;cin >> n;vector<string> nums(n);for (int i = 0; i < n; ++i) {cin >> nums[i];}sort(nums.begin(), nums.end(), cmp);string ans = "";for (auto& i : nums) ans += i;// 去除前导0bool fro_zero = true;for (auto& i : ans) {if (fro_zero && i != '0') {fro_zero = false;}if (!fro_zero) cout << i;}// 如果全是0，输出0if (fro_zero) cout << 0;cout << endl;
}