最大数字
原题链接
🥰提交结果
思路
-
对于每一位,我我们都要
尽力到达 9
所以我们去
遍历每一位
, 如果是9
直接跳过这一位如果可以
上调
到9
我们将这一位上调到9
,并且在a
中减去对应的次数同样的,如果可以
下调
到9
,我们将这一位下调到9
,并且在b
中减去对应的次数如果上调和下调的
次数都不够
,就按找能加就加
的原则 例如:
3->9 a=1 b=1
3
想要到达9
,上调
的次数不足以使他到达9
,同样下调
也不行,这个时候,全加上
就可以了,同时别忘记扣除对应次数。
这里要注意,并不是上调或下调到9
的次数小就选次数少的,两种选法是不一定的:
-
3327621916603411 7 9
对于这个测试用例,每一位就可以存在两种操作,上调或者下调,两种都要试一遍,最后取得最大值是答案。(如果不考虑加和减的顺序,最后测试点通过情况只能拿
97分
,亲身实践!)
代码
#include <iostream>
#define int long long
using namespace std;
//特殊测试用例: 3327621916603411 7 9
inline string maxNum1(string st, int a, int b) {
for (int i = 0; i < st.length(); i++) {
int x = st[i] - '0';
int up = 9 - x;
int down = x + 1;
if (x == 9) {
continue;
} else if (up <= a) { //能够上调
x += up;
a -= up;
} else if (down <= b) { //能够下调
b -= down;
x = 9;
} else if (up > a) {
x += a;
a = 0;
} else if (a == 0 && b == 0) break;
st[i] = x + '0';
}
return st;
}
inline string maxNum2(string st, int a, int b) {
for (int i = 0; i < st.length(); i++) {
int x = st[i] - '0';
int up = 9 - x;
int down = x + 1;
if (x == 9) {
continue;
} else if (down <= b) {
b -= down;
x = 9;
} else if (up <= a) {
x += up;
a -= up;
} else if (up > a) {
x += a;
a = 0;
} else if (a == 0 && b == 0) break;
st[i] = x + '0';
}
return st;
}
inline string findMax(string a, string b) {
if (a > b) return a;
else return b;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int a, b;
string st;
cin >> st;
cin >> a >> b;
st = findMax(maxNum1(st, a, b), maxNum2(st, a, b));
cout << st << endl;
}