第十三届蓝桥杯C++B组国赛D题——最大数字（AC）

分手后的思念是犯贱 2023-09-28 23:11 12阅读 0赞

#### 目录 ####

*  1.最大数字
 *   *  1.问题描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.数据范围
     *  7.原题链接
 *  2.解题思路
 *  3.模板代码

## 1.最大数字 ##

### 1.问题描述 ###

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

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

你现在总共可以执行 1 号操作不超过  A A A 次, 2 号操作不超过  B B B 次。 请问你最大可以将  N N N 变成多少?

### 2.输入格式 ###

第一行包含 3 个整数:  N , A , B N, A, B N,A,B

### 3.输出格式 ###

一个整数代表答案。

### 4.样例输入 ###

123 1 2

### 5.样例输出 ###

933

### 6.数据范围 ###

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

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

### 7.原题链接 ###

[最大数字][Link 1]

## 2.解题思路 ##

看上去 N N N的范围貌似很大，达到了`1e17`的范围，但其实我们最多只需要考虑这最多`17`位数，所以可以想到爆搜得到答案。

一个数的大小是从左到右依次判断，所以我们从最左边开始枚举，我们无需关注后面的数，要利用自己的`1`号操作和`2`号操作**保证当前这个数位的数一定要尽可能最大**

然后分别考虑两种操作，首先两种操作不可能混用，因为它们是抵消的效果，所以要么对这个数全使用`1`操作，要么`2`操作。假设某个数位的值为`x`,首先考虑`1`号操作，使用后可以让该数位变大，出于**贪心**考虑，我们想让它变成`9`，那么需要进行`9-x`次`1`号操作，当然可能此时`1`号操作并不足以让我们将`x`变成`9`，但我们还是使用剩余的全部的次数将其变大，所以每次考虑`1`号操作应该使用的操作数`t`应该为`t=min(n,9-x)`,此时`x`将变为`x+t`，然后进行下一位的判断。

其次我们考虑`2`号操作，这个的判断比较简单，它是让某个值减小，唯一能让某个数变大的机会就是将其减到`0`后再减就会变成`9`。那么这样操作需要的次数就是`x+1`，如果操作次数不够，那我们宁愿不使用，因为这只会让这个数位变得更小。

在深搜`dfs`的过程中，参数记录遍历到第几个数位以及此时累计的和，当搜索完所有数位后，将此时的和与答案进行一个取`max`，最后的值则为答案。

## 3.模板代码 ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    
    char c[20];
    LL ans=0;
    //n:1号操作剩余次数  m:2号操作剩余次数
    int n,m;
    void dfs(int i,LL v){
        
    	int x=c[i]-'0';
    	if(c[i]){
        
    		//应该使用的操作次数
    		int t=min(n,9-x);
    		n-=t;
    		dfs(i+1,v*10+x+t);
    		//回溯
    		n+=t;
            //考虑操作2是否能够使用
    		if(m>x){
        
    			m-=x+1;
    			dfs(i+1,v*10+9);
                //回溯
    			m+=x+1;
    		}
    	}else{
        
            //答案取max
    		ans=max(ans,v);
    	}
    }
    int main() 
    {
        
    	scanf("%s%d%d",c,&n,&m);
    	dfs(0,0);
    	printf("%lld\n",ans);
        return 0;
    }

[Link 1]: https://www.lanqiao.cn/problems/2193/learning/