蓝桥杯每日真题

蓝桥杯每日真题 - 第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；
- 两种结果之间选择更优解。