蓝桥杯每日真题 - 第17天

题目：（最大数字）

题目描述（13届 C&C++ B组D题）

题目分析： 

• 操作规则：

  • 1号操作：将数字加1（如果该数字为9，变为0）。

  • 2号操作：将数字减1（如果该数字为0，变为9）。

• 目标：

  • 通过操作，将数字尽可能变大。

• 限制：

  • 总操作次数受限于 A 次1号操作和 B 次2号操作。

• 核心问题：

  • 在有限操作次数内，如何分配操作次数，使结果数字最大化？

解题思路：

1. 优先级策略：

   • 优先将当前位变成9，因为9是所有个位数中最大的数；

   • 根据剩余操作次数，依次考虑其他位。

2. 递归解决：

   • 每次递归针对某一位：

     • 尝试使用1号操作尽量向9靠拢；

     • 尝试使用2号操作绕过0靠拢9；

     • 比较两种策略下的最终结果，选择字典序更大的路径。

3. 终止条件：

   • 遍历到数字的末尾；

   • 可用操作次数（A 或 B）为0。

4. 动态更新数字：

   • 通过字符串的直接修改，更新当前数字。

代码实现（C语言）：

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>
#include<string.h>void foo(char N[], int n, int a, int b) {if (N[n] == '\0') {return;}int poDis, neDis;int na, nb;char Na[20], Nb[20];poDis = 9 - (N[n] - '0');neDis = 10 + (N[n] - '0') - 9;if (a >= poDis && b >= neDis) {N[n] = '9';strcpy(Na, &N[n + 1]);strcpy(Nb, &N[n + 1]);foo(Na, 0, a - poDis, b);foo(Nb, 0, a, b - neDis);if (strcmp(Na, Nb) >= 0) {strcpy(&N[n + 1], Na);}else {strcpy(&N[n + 1], Nb);}}else if (a >= poDis) {a -= poDis;N[n] = '9';foo(N, n + 1, a, b);}else if (b >= neDis) {b -= neDis;N[n] = '9';foo(N, n + 1, a, b);}else {na = N[n] - '0' + a;nb = (10 + N[n] - '0' - b) % 10;if (na > nb) {N[n] = na + '0';a = 0;foo(N, n + 1, a, b);}else if (na < nb) {N[n] = nb + '0';b = 0;foo(N, n + 1, a, b);}else {N[n] = na + '0';strcpy(Na, &N[n + 1]);strcpy(Nb, &N[n + 1]);foo(Na, 0, 0, b);foo(Nb, 0, a, 0);if (strcmp(Na, Nb) >= 0) {strcpy(&N[n + 1], Na);}else {strcpy(&N[n + 1], Nb);}}}
}int main() {char N[20];int a, b;// inscanf("%s%d%d", N, &a, &b);// mainfoo(N, 0, a, b);// outprintf("%s", N);return 0;
}

 

得到运行结果：

代码分析： 

• 递归函数设计：

  • 参数包括当前处理的位数、剩余的1号和2号操作次数。

  • 每次递归后更新字符串，并返回最佳结果。

• 字符串操作：

  • 为了保持数字位数的变化状态，利用字符串操作更新数字。

• 状态转移：

  • 如果可以使用1号操作，则递归尝试将当前位增加到9；

  • 如果可以使用2号操作，则递归尝试将当前位绕过0变成9；

  • 两种结果之间选择更优解。

 

难度分析

⭐️⭐️⭐️⭐️

 

总结

本题通过递归枚举所有可能的操作路径，并选择字典序最大的结果数字。通过合理的操作分配和优先级选择，可以在操作次数受限的情况下达到优化效果。递归的设计逻辑清晰，代码实现具有较好的通用性和扩展性。