蓝桥杯每日真题 - 第17天
题目：（最大数字）
题目描述（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;
// in
scanf("%s%d%d", N, &a, &b);
// main
foo(N, 0, a, b);
// out
printf("%s", N);
return 0;
}
得到运行结果：
代码分析：
-
递归函数设计：
-
参数包括当前处理的位数、剩余的1号和2号操作次数。
-
每次递归后更新字符串，并返回最佳结果。
-
-
字符串操作：
-
为了保持数字位数的变化状态，利用字符串操作更新数字。
-
-
状态转移：
-
如果可以使用1号操作，则递归尝试将当前位增加到9；
-
如果可以使用2号操作，则递归尝试将当前位绕过0变成9；
-
两种结果之间选择更优解。
-
难度分析
⭐️⭐️⭐️⭐️
总结
本题通过递归枚举所有可能的操作路径，并选择字典序最大的结果数字。通过合理的操作分配和优先级选择，可以在操作次数受限的情况下达到优化效果。递归的设计逻辑清晰，代码实现具有较好的通用性和扩展性。
原文地址：https://blog.csdn.net/weixin_74066588/article/details/143868327
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！