森罗结界

chen_zhe · 2022-09-10 20:53:55 · 题解

可以通过观（数）察（数），发现从 0 到 9 的这十个整数所需要的 \texttt * 数量分别为 24,5,8,15,30,23,11,16,10,18。

最大的数字自然有着最多的位数，由于 1 所用的 \texttt * 数量最少，因此可以想到多放一些 1。例如说，你用 10 个 \texttt *，你能写出一个 8，也可以写出一个 11，那么 11>8，自然写 8 是不优的了。

但是当位数相同的情况下，填 1 有时候会吃亏，例如说有 13 个 \texttt *，你可以写 11，也可以写 21，这个时候写 21 是最优的。而且这个时候为了让数字尽可能大，你要把这个大的数字放在首位。

实际上我们会发现只有 2 是要特别考虑的数字，因为其他的数字所需要用的 \texttt * 的数量都大于等于两倍的填 1 所用的 \texttt *，也就是写上一个数字 x 所用的 \texttt * 可以被用至少两个 1 取代，在位数上就不优了。

那么在什么时候要将 2 放在首位呢？只要填上这个 2 之后位数不会因此减少即可，也就是当你不断地写 1，写到所剩的 \texttt * 个数还有 8 或者 9 个的时候填上 2，再将你所写的这一串数字反过来即可。

如果要更为简单的写法，根据上述的分析我们会发现这个填写 2 的策略等价于当 n \equiv 3,4\pmod 5 时，首位填上 2 是最优的。因此根据这个思路可以完成代码如下：

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int cnt1=n/5,cnt2=n%5;
    if (cnt2>=3)
    {
        cnt1--;
        cout << "2";
    }
    for (int i=1;i<=cnt1;i++)
        cout << "1";
    return 0;
}