题解 CF1593B Make it Divisible by 25
智子
2021-10-14 22:13:46
## 题意
输入一个正整数 $n$，删去若干位数使其能被 25 整除，求最少要删去多少位数字。
数据范围：$25 \leq n \leq 10^{18}$
## 思路
25 的倍数的特征很简单：末尾两位数是 00、25、50、75，所以我们可以考虑进行贪心：
从最后一位出发，找到最低位的 0 和最低位的 5，记录为第 $p$ 位和第 $q$ 位。
然后再从第 $p$ 位出发，向左找到遇到的第一个 0 或 5，将这两位后面的所有数都删去，更新答案；从第 $q$ 位出发，向左找到遇到的第一个 2 或 7，将这两位后面的所有数都删去，更新答案。
## 代码
代码实现比较简单，但要注意细节。
```cpp
#include<iostream>
using namespace std;
const int MAXN = 100 + 5;
int a[MAXN];
int len = 0;
int main() {
int T;
cin >> T;
while(T--) {
long long n;
cin >> n;
len = 0;
long long t = n;
while(t != 0) {
a[++len] = t % 10;
t /= 10;
}
int p = len, q = len, ans = len;
for(int i = len; i >= 1; i--) {
if(a[i] == 0) {
p = i;
} else if(a[i] == 5) {
q = i;
}
}
for(int i = p + 1; i <= len; i++) {
if(a[i] == 0 || a[i] == 5) {
ans = min(ans, i - 2);
}
}
for(int i = q + 1; i <= len; i++) {
if(a[i] == 2 || a[i] == 7) {
ans = min(ans, i - 2);
}
}
cout << ans << endl;
}
return 0;
}
```