今天刚做完了微软暑期实习的在线编程比赛。总体来说，相较于去年微软校招的在线笔试，难度小了不少。
在这里必须吐槽一下，本次比赛的第二、第三题给出的C++模板有问题，导致很多同学浪费了不少时间，希望下次微软出题的时候可以严谨一些。

第一题

给出一个数$X$，$-10^5 \le X \le 10^5$，可以随意改变$X$中数字的顺序，问可以得到的最小数是多少。要求得到的数不允许有前导0。

样例

输入：301，输出：103
输入：-8139，输出：-9831

算法

(排序) $O(nlogn)$

一个很直观的想法：要想得到最小数，我们只要把所有数字从小到大排序即可。
有两个要注意的地方：

1. 处理前导0：把最小的非零数字换到首位即可。
2. 处理负数：这里利用C++的特性，对正数取模会得到正余数，对负数取模会得到负余数。例如 $-8139 \% 10 = -9$，所以我们对所有数字从小到大排序时，$-9$会排在最前面， 而这正是我们想要的。因此处理负数时，代码不需要做任何修改！

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int get_minimum_number(int x)
{
    if (!x) return 0;

    vector<int> nums; // 存储X的所有数位
    while (x)
    {
        nums.push_back(x % 10); // 依次取出X的所有数位
        x /= 10;
    }
    sort(nums.begin(), nums.end());
    int k = 0;
    while (nums[k] == 0) k++;
    swap(nums[0], nums[k]); // 处理前导0，把最小的非零数字换到首位
    int res = 0;
    for (int i = 0; i < nums.size(); i++) res = res * 10 + nums[i]; // 把各个数位拼成一个整数
    return res;
}

int main()
{
    int x;
    cin >> x;
    cout << get_minimum_number(x) << endl;
    return 0;
}