贪心算法实战：GCJ整洁数问题解析与C++实现

1. 项目概述与问题拆解最近在带学生准备信息学奥赛信奥和Google Code JamGCJ这类算法竞赛时我发现一个非常经典且高频的题目类型处理数字的性质。今天要聊的这道题——P13159 [GCJ 2017 Qualification] Tidy Numbers就是其中的佼佼者。它不仅是GCJ资格赛的题目也频繁出现在信奥的练习题库中考察的核心是选手对数字的遍历、贪心思维和边界条件的处理能力而不是复杂的数学公式。很多初学者一看到“数字”、“非递减”这些字眼可能会试图去推导数学规律结果往往陷入死胡同。实际上这类题的解法非常“工程化”需要的是清晰的逻辑和细致的实现。所谓“Tidy Number”整洁数定义很简单一个整数的各位数字从左到右是非递减的即每个数字都不小于它左边的数字。例如123, 1133, 555 都是整洁数而 132, 103, 321 就不是。题目通常会给一个很大的数 N比如长达18位对应C的long long上限要求你找出不大于 N 的最大整洁数。这题的核心难点在于你不能简单地暴力枚举因为N可能非常大。我们需要一种高效的算法从高位向低位扫描找到第一个“破坏”非递减性质的位置然后对其进行调整。这个调整过程就是贪心算法的典型应用为了得到最大的可能数我们在尽可能高的位上减少得越少越好。接下来我会结合C实现把这道题的解题思路、代码细节以及我踩过的坑毫无保留地分享给你。2. 核心思路与算法设计2.1 问题转化与贪心策略面对一个像N 1329这样的数字我们的目标是从左到右检查。理想情况下我们希望结果尽可能接近N所以会尝试保持高位不变。扫描过程如下找到第一个满足digit[i] digit[i1]的位置i。这意味着从i开始序列不再“整洁”。在1329中比较 ‘3’ 和 ‘2’发现 3 2所以位置i1第二位是第一个破坏点。关键操作来了我们不能直接把这个破坏点digit[i]改小因为这样可能使得它小于digit[i-1]破坏前面的整洁性。正确的做法是将digit[i]的值减1然后将i之后的所有位都设置为 ‘9’。为什么是9因为我们要在i位已经减小的情况下让后面的位数尽可能大这样才能保证最终结果是最大的。对于1329在i1数字‘3’处减1变成‘2’后面全变‘9’得到1299。但是这还没完。减1操作可能导致新的问题digit[i]减1后可能小于digit[i-1]。例如N 1332第一个破坏点在i2比较 ‘3’ 和 ‘2’。如果只将第三个‘3’减1变成‘2’得到1329此时第二位‘3’和新的第三位‘2’又构成了递减关系32结果1329本身也不是整洁数。所以我们需要一个“回溯”或“连续减”的过程当在某一位减1后必须检查它是否小于前一位如果是则前一位也需要减1并继续向前检查。这个过程一直持续到数字序列重新满足非递减条件为止然后将当前位之后的所有位设为‘9’。这个“找到破坏点向前借位后面补9”的策略就是本题的贪心核心。它保证了我们得到的数是最大的因为我们是在最高的可能位上进行了最小的减少减1并将减少的影响通过补9最大化地弥补回来。2.2 算法步骤详解将上述策略转化为清晰的算法步骤输入与转换将输入的长整数 N 转换为字符串str方便逐位操作。扫描寻找破坏点从下标i 0开始遍历到len-2比较str[i]和str[i1]。处理破坏点 a. 一旦找到str[i] str[i1]记录位置pos i。 b. 从pos开始向前回溯 (pos--)只要str[pos] str[pos-1]或者str[pos]减1后小于str[pos-1]就继续向前移动pos。这个循环的目的是找到第一个可以安全减1且不会破坏前面非递减性质的位置。实际上更直接的实现是在找到第一个str[i] str[i1]后执行str[i]--然后令j i只要j 0且str[j] str[j-1]就执行str[j-1]--并j--。这样j最终停留的位置就是最后一个被减1的位。 c. 将j位置之后的所有位即str[j1]到末尾都设置为 ‘9’。处理前导零经过上述操作数字可能变成像0999这样带有前导零的形式。我们需要将前导零去除。输出结果输出处理后的字符串。这个算法的时间复杂度是 O(L)其中 L 是数字的位数最多18效率极高。空间复杂度主要是存储字符串的 O(L)。2.3 为什么贪心算法有效这里涉及一个贪心选择性质的证明。我们的目标是找到不大于N的最大整洁数。假设我们找到了第一个破坏点 i。如果我们不在 i 处进行调整那么任何包含原始str[i]和str[i1]的子序列都不可能构成整洁数。因此调整是必须的。调整时有两种可能调小str[i]或者调小更前面的某一位。如果我们调小更前面的位比如str[i-1]那么为了最大化最终数值我们必须把从被调小那位开始后面的所有位都设为 ‘9’。但是这会导致在更高位上进行了减少显然得到的数会比在str[i]处减少得到的数要小。例如N321在i1‘2’处减1得299在i0‘3’处减1得299这个例子巧合相同但如果N331在i1处减1得329在i0处减1得299329299。因此在最靠后的破坏点进行减少是最优的。而我们算法中的回溯过程正是为了处理减少后可能引发的连锁反应确保找到的正是那个“最靠后的、能够安全减1的位置”。注意一个非常常见的错误是只将找到的第一个破坏点减1后面补9而不进行向前回溯检查。这会在遇到N1332或1000这样的案例时失败。1000的第一个破坏点在i2比较第二个‘0’和第三个‘0’相等继续比较第三个‘0’和第四个‘0’相等继续...等等1000中10第一个破坏点其实是i0。处理1000str[0]--变成0后面全变9得到0999去前导零得999。这要求我们的算法能正确处理最高位就是破坏点的情况。3. C代码实现与逐行解析理解了算法我们来看C代码如何实现。我会提供两个版本的代码一个清晰易懂的版本和一个优化后的简洁版本并详细解释关键点。3.1 清晰实现版#include iostream #include string using namespace std; string lastTidyNumber(string num) { int n num.size(); // 标记最后一个需要调整的位置 int adjustPos -1; // 1. 从左到右扫描找到第一个递减的位置 for (int i 0; i n - 1; i) { if (num[i] num[i 1]) { adjustPos i; // 找到后不能直接break需要继续向前回溯的可能 // 但我们可以先记录这个位置然后开始调整 break; } } // 如果没有找到递减对说明数字本身就是Tidy直接返回 if (adjustPos -1) { return num; } // 2. 关键的回溯调整过程 // 将adjustPos位置的数字减1 num[adjustPos]--; // 向前检查如果减1后导致它小于前一位则需要继续向前借位 int j adjustPos; while (j 0 num[j] num[j - 1]) { num[j - 1]--; j--; } // 3. 将j位置之后的所有位都设置为9 for (int k j 1; k n; k) { num[k] 9; } // 4. 处理可能的前导零例如输入是1000输出会变成0999 int start 0; while (start n - 1 num[start] 0) { // 保留最后一位即使它是0数字就是0 start; } return num.substr(start); } int main() { // 示例处理多个测试用例 string test_cases[] {132, 1000, 7, 111111111111111110, 1332}; for (string n : test_cases) { cout N n - Last Tidy lastTidyNumber(n) endl; } return 0; }代码关键点解析字符串操作使用string类型存储数字比直接操作整数更灵活可以处理任意长度的数字虽然本题限制在long long范围内。adjustPos的查找循环for (int i 0; i n - 1; i)寻找第一个num[i] num[i1]的位置。这里用break是因为我们只需要第一个破坏点作为调整的起点。回溯循环while (j 0 num[j] num[j - 1])这是算法的核心。j从adjustPos开始如果当前位减1后小于前一位说明前一位也需要减1。循环持续向前直到序列重新满足非递减条件。例如N1332adjustPos 2(num[2]‘3’ num[3]‘2’)num[2]--- ‘2’现在数字是”1322“注意我们还没改后面j2检查num[2] (‘2’) num[1] (‘3’)成立所以num[1]--- ‘2’j1。数字变为”1222“。j1检查num[1] (‘2’) num[0] (‘1’)不成立。循环结束。最终j1。补9操作for (int k j 1; k n; k)将j之后所有位设为 ‘9’。对于上面的例子从k2开始num[2]和num[3]变为 ‘9’得到”1299“。去除前导零while (start n - 1 num[start] 0)这个循环跳过开头的 ‘0’。条件是start n - 1意味着如果整个数字变成了”0“比如输入就是”1“减1后不对输入”1“本身就是整洁数不会进入调整流程。输入”10“呢调整后是”09“去前导零得”9“我们会保留最后一个零。substr(start)返回从第一个非零字符开始的子串。3.2 优化简洁版清晰版便于理解但代码可以写得更紧凑逻辑也可以整合在一个循环里。下面是一个更常见的竞赛写法#include iostream #include string using namespace std; string lastTidyNumber(string s) { int n s.length(); // 整合查找和回溯过程 for (int i n - 2; i 0; --i) { if (s[i] s[i 1]) { s[i]--; // 将i之后的所有位置为9 for (int j i 1; j n; j) { s[j] 9; } // 关键由于s[i]减1了可能导致s[i-1] s[i]需要继续处理 // 这里采用一个技巧让i回退以便外层循环的下一次迭代能检查到 s[i-1] 和新的 s[i] // 但更常见的做法是在置9后重新从i开始向前扫描检查。 // 我们换一种思路找到第一个破坏点后直接向前循环处理借位。 } } // 上面的写法有缺陷它没有处理连锁借位。下面是一个正确的简洁版。 } // 正确的简洁实现 string lastTidyNumber_correct(string s) { int n s.length(); int pos n; // 记录第一个需要开始变9的位置 for (int i n - 1; i 0; --i) { if (s[i] s[i - 1]) { // 发现递减 s[i - 1]--; // 前一位减1 pos i; // 从i开始后面的位都要变成9 } } for (int i pos; i n; i) { s[i] 9; } // 去除前导零 int start 0; while (start n - 1 s[start] 0) start; return s.substr(start); }优化版解析这个版本采用了从后向前扫描的技巧更加巧妙。从倒数第二位 (i n-1) 向前扫描到第一位 (i 1)。如果发现s[i] s[i-1]这说明s[i-1]太大了破坏了整洁性。那么就将s[i-1]减1并记录下位置pos i。注意pos记录的是第一个需要被设置为 ‘9’ 的位置。为什么从后往前因为当我们把s[i-1]减1后它可能就小于s[i-2]了。但是别急我们的循环是向前的下一次迭代就会检查i-1和i-2的关系。如果s[i-1](已经减1) 确实小于s[i-2]那么s[i-2]也会被减1并且pos会被更新为i-1。这个过程自动处理了连锁借位。扫描完成后pos指向的就是最后一个被减1的数字的下一位从这个位置开始到末尾全部设置为 ‘9’。最后去除前导零。以N1332为例i3: 比较 s[3]‘2’ 和 s[2]‘3’23所以 s[2]-- - ‘2’ pos3。i2: 比较 s[2]‘2’ (新值) 和 s[1]‘3’23所以 s[1]-- - ‘2’ pos2。i1: 比较 s[1]‘2’ (新值) 和 s[0]‘1’21不操作。循环结束从 pos2 开始置9s[2]‘9’ s[3]‘9’得到”1299“。这个版本逻辑更统一代码更短是竞赛中的推荐写法。3.3 输入输出与性能考量在信奥或GCJ系统中通常需要处理多个测试用例。完整的代码框架如下#include iostream #include string using namespace std; string solve(string s) { int n s.length(); int pos n; for (int i n - 1; i 0; --i) { if (s[i] s[i - 1]) { s[i - 1]--; pos i; } } for (int i pos; i n; i) s[i] 9; // 去除前导零 int start 0; while (start n - 1 s[start] 0) start; return s.substr(start); } int main() { // 假设输入第一行是测试用例数T int T; cin T; for (int case_num 1; case_num T; case_num) { string N; cin N; string ans solve(N); cout Case # case_num : ans endl; } return 0; }性能与注意事项复杂度O(L * T)对于每个长达18位的数字操作都是常数次遍历完全在限制内。数据类型必须使用string处理输入。即使N在long long范围内如果直接用整数类型实现减1和置9的逻辑会非常繁琐且容易出错特别是涉及前导零时。去前导零这是极易忽略的一步。考虑N100答案应为99。如果不处理输出会是”099“。4. 常见错误与调试技巧即便思路清晰实现时也容易掉进一些坑里。下面是我在教学中总结的学员常见错误和对应的调试方法。4.1 典型错误案例错误1只减1不回溯// 错误代码示例 string wrong1(string s) { for (int i 0; i s.size()-1; i) { if (s[i] s[i1]) { s[i]--; for (int j i1; j s.size(); j) s[j] 9; break; } } return s; }输入1332期望1299实际输出1329。原因在i2处将 ‘3’ 减为 ‘2’ 后新的 ‘2’ 小于前面的 ‘3’结果1329中32仍然不整洁。错误2回溯逻辑错误// 另一种错误回溯 string wrong2(string s) { int pos -1; for (int i 0; i s.size()-1; i) { if (s[i] s[i1]) { pos i; break; } } if (pos ! -1) { s[pos]--; // 错误只向前检查一位 if (pos 0 s[pos] s[pos-1]) { s[pos-1]--; } for (int i pos1; i s.size(); i) s[i] 9; } return s; }输入1000期望999实际输出0999(去零前)。过程pos0s[0]-- - ‘0’检查 s[0] (‘0’) s[-1]? 不检查。后面置9得0999。问题在于最高位减1后变成 ‘0’但算法没有继续向前也没法向前导致结果有前导零。这需要正确的去零逻辑。但更隐蔽的错误在N322期望299。pos1(s[1]‘2’ s[2]‘2’? 不是相等。等等322的第一个破坏点在i0(32)。所以pos0s[0]-- - ‘2’检查 s[0] (‘2’) s[-1]? 不检查。后面置9得299。这个例子碰巧对了。但对于N332pos1(32)s[1]-- - ‘2’检查 s[1] (‘2’) s[0] (‘3’) 成立所以 s[0]-- - ‘2’。后面置9得299。正确。但这个逻辑对于连续多个需要减1的情况可能处理不全不如从后向前的算法健壮。错误3忽略去前导零这是最常犯的输出格式错误。在调试时务必测试边界情况1,10,100,1000,1110。错误4输入读取错误题目可能输入的是数字字符串也可能直接是整数。务必看清题目要求。对于GCJ这道题输入是数字字符串。如果误用long long读取虽然能通过部分样例但无法处理非常大的数字尽管本题N在long long范围但用字符串处理更通用、更安全。4.2 调试与测试策略设计全面的测试用例输入预期输出检查点77本身就是整洁数132129普通递减1000999最高位递减产生前导零11111111111111111099999999999999999长数字中间递减13321299需要连锁回溯109两位数最高位递减999999全是9整洁数120119递减发生在中间但借位影响高位120-119检查12, 20破坏点在‘2’和‘0’‘2’减1变‘1’后面变9得119正确。121119121-11912, 21破坏点在‘2’和‘1’‘2’减1变‘1’后面变9得119。注意119是整洁数且是小于121的最大整洁数。使用调试输出在算法关键步骤打印中间变量。string solve_debug(string s) { cout “Input: “ s endl; int n s.length(); int pos n; for (int i n - 1; i 0; --i) { if (s[i] s[i - 1]) { cout “Found decrease at “ i-1 ” and “ i “: “ s[i-1] “” s[i] endl; s[i - 1]--; pos i; cout “After decrement: “ s endl; } } cout “Position to set to ‘9’: “ pos endl; for (int i pos; i n; i) s[i] ‘9’; cout “After setting 9s: “ s endl; // … 去零 return s; }对比两种算法实现清晰版和优化版用同一组测试用例运行确保结果一致。这能帮助验证优化版逻辑的正确性。边界条件测试最小输入1最大输入10^18 - 1即999999999999999999(18个9)全递减987654321全递增123456789有零的数字101,10014.3 从错误中学习的经验贪心策略的证明意识不是所有贪心都是显而易见的。在想到“找到第一个破坏点就减1后面补9”后要主动去构造反例如1332来验证。如果发现反例就要思考如何修补策略引入回溯。这比盲目调试更高效。字符串操作的陷阱s[i]--操作的是字符例如‘3’--会得到‘2’的ASCII码结果还是字符‘2’这是正确的。但要小心不要写成s[i] - 1虽然效果相同但s[i]--更直观。另外确保索引i在有效范围内。循环边界无论是从前向后还是从后向前扫描循环的起止下标很容易出错。从后向前扫描时for (int i n - 1; i 0; --i)确保比较的是s[i]和s[i-1]。如果写成i 0会导致s[-1]的访问。去零逻辑的细节while (start n - 1 s[start] ‘0’)中的n - 1确保了像”0“这样的字符串不会被全部删光至少保留一位。这是处理数字0的必要条件。5. 算法扩展与相关题型掌握了“整洁数”这道题你就掌握了一类“数字位处理贪心”问题的通用解法。我们可以看看它的几种变体和相关题目。5.1 变体寻找大于N的最小整洁数如果题目改为寻找大于N的最小整洁数思路就完全不同了。这时我们需要找到第一个str[i] str[i1]的位置吗不完全是。例如N1231大于它的最小整洁数是1233将最后的1增加为3不1232不是整洁数因为23? 1232中 12, 23, 32不是整洁数。实际上大于N的最小整洁数可以通过“进位”思想来解决。从最低位开始尝试增加如果增加后导致该位大于前一位则考虑向前进位并将当前位及之后设为该位允许的最小值对于整洁数最小值是前一位的数字。这比找最大整洁数更复杂一些但核心仍是贪心和模拟。5.2 相关信奥/GCJ题型数字重组类给定一个数字通过重新排列其数字可能允许删除一些数字来得到最大/最小的满足某种条件的数如能被某数整除、是回文数等。这类题通常需要结合数位DP或贪心。单调数字和整洁数几乎一样有时要求严格递增或非递增。解法完全相同。下一个排列/上一个排列给定一个数字序列求出其在字典序中的下一个排列。这是C标准库next_permutation的功能但要求自己实现时就需要类似的从后向前查找、交换、反转的过程。整洁数可以看作是寻找“上一个整洁排列”。数位DP问题当约束条件更复杂如包含特定数字、数字和满足条件且N的范围极大时就需要用数位DP来统计区间内满足条件的数的个数。整洁数问题如果问“区间 [L, R] 内有多少个整洁数”数位DP是标准解法。5.3 如何练习巩固手动模拟拿纸笔模拟算法过程尤其是对于1332,1000,120这样的案例一步步写出字符串的变化。这是理解算法最好的方式。独立实现关闭本文尝试自己从头实现一遍代码。实现后用上面的测试用例验证。提交评测在信奥如洛谷P13159或GCJ的练习平台找到原题提交确保能通过所有测试点。尝试变体自己提出变体问题并尝试解决例如“找出恰好有K位非递减的数字”或者“计算[1, N]中整洁数的个数”。这道题的价值不仅在于其解法更在于它训练了一种严谨的模拟和贪心思维。在竞赛中清晰的思路和稳健的代码实现往往比知道更多高深算法更重要。我个人的体会是每次重刷这类题目都会对边界条件有新的认识。比如最近一次给学生讲课时我特意构造了N100...0这种案例让他们深刻理解去前导零的重要性。编程的细节决定成败这句话在算法实现里体现得淋漓尽致。