📝 题目大意

给定正整数 $N$，在所有满足 $f(x) = N$（$f(x)$ 表示 $x$ 的各位数码之和）的正整数 $x$ 中，求 $f(2x)$ 的最大值 $M_{\max}$，以及使得 $f(2x) = M_{\max}$ 的最小 $x$。

💡 解题思路

1. 题目分析：核心是研究"乘以 2"对数码和的影响。当 $x$ 逐位乘以 2 时，若某一位产生进位（$2 \times d_i \ge 10$），会导致该位的数码和贡献比"无进位"少 9。因此 $f(2x) \le 2 \cdot f(x) = 2N$，等号成立当且仅当所有位都不产生进位，即 $x$ 的每一位数字都 $\le 4$。

2. 算法推导：

   • 求 $M_{\max}$：既然 $f(2x) \le 2N$ 且我们可以通过让 $x$ 只含数字 $0 \sim 4$ 来达到 $2N$（无进位），所以 $M_{\max} = 2N$。
   • 求 $x_{\min}$：在"每一位 $\le 4$"的约束下，为了最小化 $x$ 的数值，需要位数尽可能少（即每位尽可能大）。最大允许的数字是 $4$，因此贪心地用尽可能多的 $4$ 来凑 $N$：
     • 令 $N = 4q + r$，其中 $0 \le r < 4$。
     • 若 $r > 0$，$x_{\min}$ 为 $r$ 后面接 $q$ 个 $4$。
     • 若 $r = 0$，$x_{\min}$ 为 $q$ 个连续的 $4$。
   • 此构造与 std.cpp 完全一致：先输出余数 $r$（如果非零），再循环输出 $q$ 个 $4$。

3. 边界与细节：

   • 当 $N$ 较小时（如 $N=1,2,3$），$x_{\min}$ 就是 $N$ 本身，无 $4$ 后缀。
   • 当 $N$ 是 $4$ 的倍数时，$x_{\min}$ 全是 $4$，没有前导余数。
   • 结果可能极大（$N=100$ 时 $x_{\min}$ 有 25 位），需用字符串或直接输出，不能用 64 位整数存储。std.cpp 中逐位 cout 输出，避免了溢出问题。

⏱️ 复杂度分析

• 时间复杂度：$O(N)$。输出 $M_{\max}$ 是 $O(1)$，输出 $x_{\min}$ 最多输出 $\lfloor N/4 \rfloor + 1$ 个数字，即 $O(N)$ 个字符。
• 空间复杂度：$O(1)$。仅使用常数个变量 n, x。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	// M_max = 2N：无进位时 f(2x) 达到理论上界
	int x = (n / 4) * 8 + (n % 4) * 2; // 等价于 2 * n
	cout << x << '\n';
	// 构造最小 x：先输出余数 r（1/2/3），再输出 q 个 4
	if (n % 4) cout << n % 4;          // 输出高位余数位
	while (n >= 4) {
		cout << 4;                     // 每位 4 保证无进位且位数最少
		n -= 4;
	}
	return 0;
}