题目描述:
C. 九进制问题
时间限制:每个测试2秒
内存限制:每个测试256兆字节
给定一个正整数 n。每次操作中,你可以给 n 加上任意一个十进制表示仅由数字 9 组成的正整数(数字 9 可以重复出现多次)。
请问至少需要进行多少次操作,才能使得数字 n 的十进制表示中至少出现一个数字 7?
例如,当 n=80 时,只需进行一次操作:你可以给 n 加上 99,操作后 n=179,其中包含了数字 7。
输入
每个测试包含多个测试用例。第一行包含测试用例数量 t(1≤t≤10^4)。接下来是每个测试用例的描述。
每个测试用例只有一行,包含一个整数 n(10≤n≤10^9)。
输出
对于每个测试用例,输出使数字 n 包含数字 7 所需的最少操作次数。
解题思路:
1.加上任意一个只有9构成的数字,999,99可以,但是99900不可以,也就是说加上了10的幂-1,所以如果进行最少l次操作找到7的话,
最终数字= n + l × (999...9)
= n + l × (10^k - 1) // 因为 999...9 = 10^k - 1
= (n - l) + l × 10^k
等价于对n-l执行某个位置加1的操作,这样for循环遍历每一位看是否可以,如若加的是9构成的数字,对某一位进行判断时会受到其他位影响,难以得出准确结果,如果当前位变成7的操作小于操作数l代表可以,并且不用再统计原本为8和9的位置,因为由8和9到的是17操作次数过多,l是从0到9,所以不用担心n-l里只有8和9的情况。
核心代码实现:
void solve() {
int n;
cin >> n;
for (int l = 0; l <= 9; l++) {
string s = to_string(n - l);
int md = 0;
for (auto c: s) {
if (c <= '7') {
md = max(md, c - '0');
}
}
if (l >= 7 - md) {
cout << l << '\n';
return;
}
}
}
