题目链接:https://codeforces.com/contest/1367/problem/C
题意
给出一个长为 $n$ 的 $01$字符串,两个相邻 $1$ 间距应大于 $k$,初始序列合法,问最多能再使多少 $0$ 变为 $1$ 。
题解
如果当前字符为 $0$,查找 $k$ 个距离内是否有 $1$:
- 若有则不合法,跳至最近的 $1$
- 否则因为 $k$ 个距离内没有 $1$,当前字符置为 $1$,跳至第 $i + k$ 个字符
如果当前字符为 $1$,因为初始序列合法,下一个可以置为 $1$ 的 $0$ 至少在第 $i + k$ 个字符后,跳至第 $i + k$ 个字符。
代码
#include <bits/stdc++.h>
using namespace std;void solve() {
int n, k; cin >> n >> k;
string s; cin >> s;
int ans = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '0') {
int j = i + 1;
while (j < s.size() and s[j] == '0' and j - i <= k) ++j;
if (j - i > k or j == s.size()) {
ans++;
i += k;
} else i = j - 1;
} else i += k;
}
cout << ans << "\n";
}int main() {
int t; cin >> t;
while (t--) solve();
}