题目分析

问题本质

给定一个大数 $n$（最多 $1000$ 位），找到距离 $n$ 最近的 Handsome 数。Handsome 数的定义是相邻数位的奇偶性不同。

核心挑战

1. 大数处理：$n$ 可达 $10^{1000}$，无法枚举
2. 多解情况：可能存在多个距离相同的解
3. 构造约束：需要保证相邻数位奇偶性交替

关键观察

Handsome 数的结构特征

Handsome 数只有两种可能的奇偶模式：

• 模式A：奇偶奇偶...（从最高位开始）
• 模式B：偶奇偶奇...（从最高位开始）

距离最近的含义

需要找到：

1. 比 $n$ 大的最小 Handsome 数
2. 比 $n$ 小的最大 Handsome 数 然后比较哪个距离更近，或者都输出。

算法框架

步骤1：检查原数

首先检查 $n$ 本身是否是 Handsome 数：

• 如果是，直接输出 $n$
• 否则继续寻找

步骤2：寻找最近的 Handsome 数

策略：从高位到低位找到第一个破坏奇偶交替的位置 $p$，然后在该位置进行调整。

具体过程：

1. 定位违规位置：找到第一个位置 $i$，使得 digit[i] 和 digit[i+1] 的奇偶性相同
2. 分类处理：
   • 情况1：尝试修复当前位，使其满足奇偶交替且尽量接近原数
   • 情况2：如果无法修复，需要回溯到前一位调整

步骤3：构造候选解

比 $n$ 大的最小 Handsome 数：

1. 找到第一个可以增加的位置 $p$
2. 在该位置尝试增加数字，使其满足奇偶交替
3. 后续位用最小合法数字填充（保持奇偶交替）

比 $n$ 小的最大 Handsome 数：

1. 找到第一个可以减少的位置 $p$
2. 在该位置尝试减少数字，使其满足奇偶交替
3. 后续位用最大合法数字填充（保持奇偶交替）

详细算法

算法流程

1. 输入处理：将 $n$ 作为字符串读入
2. 模式检测：确定原数应该遵循哪种奇偶模式
3. 违规检测：找到第一个违反奇偶交替的位置
4. 候选生成：
   • 向上搜索：从违规位置开始，尝试增加数字得到更大的 Handsome 数
   • 向下搜索：从违规位置开始，尝试减少数字得到更小的 Handsome 数
5. 结果比较：计算两个候选解与 $n$ 的距离，输出最近的解

特殊情况处理

全9数字：

• 如 $999$，比它大的最小 Handsome 数需要增加位数
• 如 $1000$ 比 $999$ 大，需要检查 $1000$ 是否是 Handsome 数

全0数字：

• 如 $100$，比它小的最大 Handsome 数需要减少位数
• 如 $99$ 比 $100$ 小，需要检查 $99$ 是否是 Handsome 数

边界情况：

• $n = 1$：输出 $1$（本身就是 Handsome 数）
• $n = 10$：输出 $9$ 和 $12$（距离都是 $1$）

构造技巧

最小填充策略

当确定前 $k$ 位后，后续位使用最小合法数字填充：

• 如果上一位是奇数，下一位填最小偶数 $0$
• 如果上一位是偶数，下一位填最小奇数 $1$

最大填充策略

当确定前 $k$ 位后，后续位使用最大合法数字填充：

• 如果上一位是奇数，下一位填最大偶数 $8$
• 如果上一位是偶数，下一位填最大奇数 $9$

复杂度分析

时间复杂度

• 检查原数：$O(L)$，其中 $L$ 是数字长度
• 生成候选解：每个候选解需要 $O(L)$ 时间
• 总复杂度：$O(L)$

空间复杂度

• 存储数字字符串：$O(L)$
• 存储候选解：$O(L)$

实现细节

大数比较

由于数字可能很大，需要实现大数减法来计算距离：

• 将数字作为字符串处理
• 实现字符串形式的大数减法
• 比较绝对值大小

多解处理

当两个候选解距离相等时，按从小到大顺序输出：

• 先输出较小的数
• 再输出较大的数

回溯处理

如果当前位无法调整到合法状态，需要回溯到前一位：

• 前一位数字加1或减1
• 检查是否产生进位或借位
• 重新确定后续位的填充

总结

本题的核心在于通过贪心构造找到最近的合法数。关键思路是从高位到低位找到第一个违规位置，然后分别向上和向下搜索最近的 Handsome 数。需要注意处理大数运算和边界情况，以及多解情况的输出顺序。