Powered by:NEFU AB-IN

Link

文章目录

• A1038 Recover the Smallest Number (30)
• • 题意
  • 思路
  • 代码

A1038 Recover the Smallest Number (30)

• 题意

  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.
  给定一个数组，数组中包含若干个整数，数组中整数可能包含前导 0。你需要将数组中的所有数字拼接起来排成一个数，并使得该数字尽可能小。

• 思路

  判断数字a, b拼凑成的数字ab还有哪个大，直接用拼接之后的字符串比较大小就可以
  即如果字符串比较ab注意是小于号，没有等于！！别管为啥了，cpm函数都这样

  所以，如果也排成最大的数也是同理

  另原理，一个集合如果能够排序，那么它一定是全序集，全序集需要满足三个性质：反对称性、传递性、完整性
  本题可证明用 return a + b < b + a; 的方法，来达到题目所需的要求，并且能够证明以上三条性质

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2023-01-09 12:57:42
  * @FilePath: \GPLT\A1038\A1038.cpp
  * @LastEditTime: 2023-01-09 13:20:26
  */
  #include 
  using namespace std;
  #define int long long
  #undef int#define SZ(X) ((int)(X).size())
  #define ALL(X) (X).begin(), (X).end()
  #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair PII;const int N = 1e5 + 10, INF = 0x3f3f3f3f;signed main()
  {IOS;int n;cin >> n;vector s(n);for (int i = 0; i < n; ++i)cin >> s[i];sort(ALL(s), [&](const string &a, const string &b) { return a + b < b + a; });string res;for (int i = 0; i < SZ(s); ++i)res += s[i];int i = 0;while (i < SZ(res) - 1 && res[i] == '0') // 去掉前导0的同时，一定要保留一位，也就是如果最后剩下0，也要保留++i;cout << res.substr(i);return 0;
  }