自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:39:56，当前版本为作者最后更新于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;
}