蓝桥杯2022年第十三届决赛真题-最大数字

解题思路:贪心，从最高位开始能变成9的就变成9，变不成9的，肯定要往大了加，这样才能变得最大。当加和减都能让某一位变成9时，回溯搜索。用全局变量m记录最大值。

注意事项:

参考代码:

#include <bits/stdc++.h>

using namespace std;

int a[20],A,B,sta[20],top=-1,len=0;

long long int num,pre,m=-1;

void dfs(int i,long long int pre)

{

    if(i>len)

    {

        m=max(m,pre);

        return ;

    }

         if(a[i]==9) dfs(i+1,pre*10+9);

         int jia=9-a[i];

         int jian=a[i]+1;

         if(jia<=A||jian<=B)

         {

            if(jia<=A)

            {

                A-=jia;

                dfs(i+1,pre*10+9);

                A+=jia;

            }

            if(jian<=B)

            {

                B-=jian;

                dfs(i+1,pre*10+9);

                B+=jian;

            }

         }

         else

         {

            int p=A;

             A=0;

             dfs(i+1,pre*10+a[i]+p);

             A=p;

         }

}

int main()

{

    cin>>num>>A>>B;

    pre=num;

    while(num>0)

    {

        sta[++top]=num%10;

        num/=10;

    }

    int i=0;

    while(top>=0)

    {

        a[++i]=sta[top--];

    }

    len=i;

    dfs(1,0);

    cout<<m<<endl;

    return 0;

}