给一个正整数 \(n\) ,在一步操作中可以移除 \(n\) 中的一个。当 \(n\) 只剩下一位时将不能再操作,如果过程中产生了前导 \(0\) ,则会被自动移除且不耗费操作次数。
询问最少需要多少次操作可以使得 \(n\) 被 \(25\) 整除。
显然一个正整数 \(x\) 若可以被 \(25\) 整除,只需要考虑最后两位。为 \(00\)、\(25\)、\(50\)、\(75\) 。此题不需要考虑前导零的处理。
于是枚举 \(00\)、\(25\)、\(50\)、\(75\) 之一。令为 \(s_i\) ,第一、二个字符为 \(s_{i_1}\) 和 \(s_{i_2}\) 。
定义初始的 \(length(n) = m\) 。
于是考虑一个算法,让指针 \(i\) 从 \(m\) 开始往前扫,当找到 \(s_{i_{l}}\) 时,\(l--\) 。当 \(l = -1\) ,\(ans = min(ans, m - i - 1)\) 并结束扫描。所有枚举结束后的 \(min\_ans\) 即答案。
view
#include <bits/stdc++.h>
typedef long long ll;
char need[][3] = {"00", "25", "50", "75"};
void solve(){
std::string s; std::cin >> s; int m = s.length(); s = " " + s;
int ans = 1 << 30;
for (int k = 0; k < 4; k++) {
int l = 1;
for (int i = m; i; --i) {
if (s[i] == need[k][l]) l--;
if (l == -1) {
ans = std::min(ans, m - i - 1);
break;
}
}
}
std::cout << ans << "\n";
}
int main() {
int _ = 1; std::cin >> _;
while (_--) {solve();}
return 0;
}