蓝桥杯每日真题

蓝桥杯每日真题 - 第17天

embedded/2024/11/19 15:00:47/

题目：（最大数字）

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

题目分析：

操作规则：
- 1号操作：将数字加1（如果该数字为9，变为0）。
- 2号操作：将数字减1（如果该数字为0，变为9）。
目标：
- 通过操作，将数字尽可能变大。
限制：
- 总操作次数受限于 A 次1号操作和 B 次2号操作。
核心问题：
- 在有限操作次数内，如何分配操作次数，使结果数字最大化？

解题思路：

优先级策略：
- 优先将当前位变成9，因为9是所有个位数中最大的数；
- 根据剩余操作次数，依次考虑其他位。
递归解决：
- 每次递归针对某一位：
  - 尝试使用1号操作尽量向9靠拢；
  - 尝试使用2号操作绕过0靠拢9；
  - 比较两种策略下的最终结果，选择字典序更大的路径。
终止条件：
- 遍历到数字的末尾；
- 可用操作次数（A 或 B）为0。
动态更新数字：
- 通过字符串的直接修改，更新当前数字。

代码实现（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；
- 两种结果之间选择更优解。