526互联

Codeforces Round 748 (Div. 3) B. Make it Divisible by 25

发布时间 2023-10-14 15:46:15作者: zsxuan

给一个正整数 \(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;
}