最大数字——蓝桥杯十三届2022国赛大学B组真题

问题分析

这道题属于贪心加回溯。所有操作如果能使得高位的数字变大必定优先用在高位，因为对高位的影响永远大于对低位的影响。然后我们再来分析一下，如何使用这两种操作？对于加操作，如果能使这一位的数字加到9则变成9，否则使这个数字尽量大。对于减操作，如果能使这一位的数字减到9则变成9，否则不采用减操作。然后我们用回溯来分别对该位进行加操作和减操作，记录最大值。时间复杂度大概是$O(2^{l{g}^n})$,不超过$10^4$的数量级。因此回溯是可行的。

AC_Code

#include <bits/stdc++.h>
using namespace std;
string result;
void dfs(string str,int i,int a,int b){if(i==str.size()||a==0&&b==0){if(result<str){result=str;}return;}char ch=str[i];if('9'-ch<=a){//能加到9 str[i]='9';dfs(str,i+1,a-('9'-ch),b);}else{//不能加到9 str[i]=ch+a;dfs(str,i+1,0,b);}if((ch-'0'+1)<=b){//能减到9 str[i]='9';dfs(str,i+1,a,b-(ch-'0'+1));}else{//不能减到9 str[i]=ch;dfs(str,i+1,a,b); }
}
int main() {string str;int a,b;cin>>str>>a>>b;dfs(str,0,a,b);cout<<result<<endl;return 0;
}