[蓝桥杯 2022 国 B] 最大数字

题目描述

给定一个正整数 $N$。你可以对 $N$ 的任意一位数字执行任意次以下 2 种操作:

1. 将该位数字加 $1$。如果该位数字已经是 $9$，加 $1$ 之后变成 $0$。

2. 将该位数字减 $1$。如果该位数字已经是 $0$，减 $1$ 之后变成 $9$。

你现在总共可以执行 $1$ 号操作不超过 $A$ 次，$2$ 号操作不超过 $B$ 次。

请问你最大可以将 $N$ 变成多少?

输入格式

第一行包含 3 个整数：$N$，$A$，$B$ 。

输出格式

一个整数代表答案。

样例 #1

样例输入 #1

123 1 2

样例输出 #1

933

提示

【样例说明】

对百位数字执行 $2$ 次 $2$ 号操作，对十位数字执行 $1$ 次 $1$ 号操作。

【评测用例规模与约定】

对于 $30 \%$ 的数据，$1 \leq N \leq 100 ; 0 \leq A, B \leq 10$

对于 $100 \%$ 的数据, $1 \leq N \leq 10^{17} ; 0 \leq A, B \leq 100$

蓝桥杯 2022 国赛 B 组 D 题。

题解

本道题目是一个贪心dfs，单纯的大暴力dfs会TLE。我们希望一个数字尽量的大，一定要设法确保他前面的位上的数字尽量向9靠近。我们从前往后处理，先处理大的数位，对于每一位，我们看看是否能通过加操作或减操作使当前位数变为9，若可以，我们就消耗加减的次数使当前位变为9，然后继续处理下一位，如果当前所剩的次数无法使当前数字变为9，我们为了使最终的数尽量的大，就应当贪心的把当前所剩的加次数全部消耗在当前位上，之后继续处理后面的数位，因为后面的数位有可能能通过减法操作变为9。

代码

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

string num, max_num;
int a, b;

// 当前处理到第pos位置，还剩下ai次加法，bi次减法
void dfs(int pos, int ai, int bi)
{
    if (pos == num.length())
    {
        max_num = max(max_num, num);
        return;
    }
    char temp = num[pos];
    if (ai >= '9' - num[pos]) // 可以通过加的方法把当前数字变为9
    {
        num[pos] = '9';
        dfs(pos + 1, ai - '9' + temp, bi);
        num[pos] = temp; // 还原
    }
    if (bi >= num[pos] - '0' + 1) // 可以通过减的方法把当前数字变为9
    {
        num[pos] = '9';
        dfs(pos + 1, ai, bi - temp + '0' - 1);
        num[pos] = temp; // 还原
    }
    if (ai < '9' - num[pos])    // 如果当前无法满足9
    {
        num[pos] = num[pos] + ai;
        dfs(pos + 1, 0, bi);
        num[pos] = temp;
    }
}

int main()
{
    cin >> num >> a >> b;
    dfs(0, a, b);
    cout << max_num << endl;
    return 0;
}

end