原题

题目

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.

输入要求

Each input file contains one test case. Each case gives a positive integer N (≤104) 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.

输出要求

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

思路

题意很简单，就是给定一个数字段，给他拼成一个最小的数。很容易想到贪心算法，但是贪的是什么？

首先想到按从小到大的顺序输出不就好了嘛，但是仔细想想不是这样的比如321>32但是321放前面才是正确的为什么呢？可以这样想假设我们下一个待选的只有a和b两个，两者是不是你在前我在后就是我在后你在前的关系，那么他们后面的数字位数一定是相同的即总位数-前面的位数-a的位数-b的位数，所以从a开始算两种选择的数字大小如下：

  1. a在前 ab*10^n
  2. b在前 ba*10^n

这样就很容易看出了，决定a和b谁在前面的方法就是比较ab以及ba的大小。

这里可能产生一个疑问，我在每一个位置的选择可不止两种啊，这么多个该怎么比较呢？

有一个巧妙地方法就是借助sort 自己实现一个cmp规则，这样排出的一定符合规则！可以尝试证明一下：

我们假设排完之后的顺序是 a b c d e f…………

使用反证法：如果该顺序不是最优解，那么一定需要通过置换变成最优解，假设我们换了a和c 那么前面从 abc变成了cba（即cba<abc） 而bc<cb bca<cba ab<ba bca<cba<cab同理 一直推到 bca<cba<cab<acb<abc; 两者相悖，所以我们的贪心策略能够得到最优解！

注意输出没有前导零，还有一个测试点需要注意就是结果为0时还要输出0（也就是说不能单纯的不输出前面的0)

AC代码

#include <bits/stdc++.h>
using namespace std;
bool cmp(string a, string b)
{
    return a + b < b + a;
}
int main()
{
    int n;
    cin >> n;
    string s[n];
    string result;
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    sort(s, s + n, cmp);
    for (int i = 0; i < n; i++)
    {
        result += s[i];
    }
    int flag = 1;
    for (int i = 0; i < result.size() - 1; i++)
    {
        if (result[i] != '0' || !flag)
        {
            flag = 0;
            cout << result[i];
        }
    }
    cout << result[result.size() - 1];
}