题目描述
有一个长为 的字符串 ，只含 0和 1 。你可以进行最多\(K\)次如下操作（ 0 次也可以）：
选择字符串 \(S\)的一个子串，将其中的字符反转（ 0变成1 ，1变成0 ）。
进行不超过\(K\)次操作后，求最长的连续的 1的长度。
数据约定
对于100%的数据：字符串只由0和1组成，长度为\(1 \leq n、k \leq 10^5\) 。
思路分析：
对于这道题而言，首先我想要发现DP，但是发现n和k都非常大，没有办法DP
继续思考，发现反转1没有任何用处，若反转的区间中有，则会将变成导致连续的区间 1 断开，所以最优情况下，反转操作只会反转连续的0，确定了这个之后，这就好写了
后来我想把连续的0的个数处理出来，找到最大的K个即可，后来发现这样的想法是错误的，因为他是连续的1的个数，有可能第一多的旁边跟着的0的个数比较小，同时连续0的个数同时相关着连续1的个数，所以不能贪心，只能枚举。
我们把题目中的连续的0合并，同时因为n非常大，我们也需要把题目中连续的1合并，对于每个0而言，处理出三个部分：
\(cnt[i] 第i个位置上共有多少个连续的0\)
\(L[i] 第i个位置上前面有多少个连续的1\)
\(R[i] 第i歌位置上后面有多少个连续的1\)
有了这个之后，我们枚举0即可，找到连续k个，但是我如果我枚举的话，就会T
最后我使用队列，这K个0肯定是连续的，枚举会造成时间的浪费，使用队列，满足k个，计算答案，同时把第一个踢出去，继续加入即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n, k;
char s[maxn];
int l[maxn], r[maxn], cnt[maxn], xx[maxn], ans, ss[maxn];
queue<int> q;
int main() {
scanf("%d%d", &n, &k);
;
scanf("%s", s + 1);
bool flag = true;
for (int i = 1; i <= n; i++) {
if (s[i] == '1') {
flag = false;
break;
}
}
if (flag == true) {
cout << n;
return 0;
}
flag = true;
for (int i = 1; i <= n; i++) {
if (s[i] == '0') {
flag = false;
break;
}
}
if (flag == true) {
cout << n;
return 0;
}
int j = 1;
for (int i = 1; i <= n; i++) {
xx[j] = s[i] - '0';
if (xx[j] == 1) {
j++;
continue;
}
while (s[i] == '0') {
cnt[j]++;
i++;
}
i--;
j++;
}
int sum = 0;
for (int i = 1; i <= j - 1; i++) {
if (xx[i] == 1)
sum++;
if (xx[i] == 0) {
l[i] = sum;
sum = 0;
}
}
int pos;
for (int i = 1; i <= j - 1; i++) {
if (xx[i] == 1)
continue;
if (xx[i] == 0)
pos = i;
i++;
while (xx[i] == 1) {
i++;
}
if (i <= j - 1) {
r[pos] = l[i];
i--;
} else
r[pos] = j - pos - 1;
}
n = 0;
for (int i = 1; i <= j - 1; i++) {
if (xx[i] == 0) {
n++;
ss[n] = 0;
int x = cnt[i];
cnt[n] = x;
x = l[i];
l[n] = x;
x = r[i];
r[n] = x;
}
}
sum = 0;
for (int i = 1; i <= n; i++) {
if (q.size() < k) {
q.push(i);
sum += l[i] + cnt[i];
}
if (q.size() == k) {
sum += r[i];
ans = max(ans, sum);
int pos = q.front();
q.pop();
sum -= r[i];
sum = sum - l[pos] - cnt[pos];
}
if (q.size() < k && i == n) {
sum += r[i];
ans = max(ans, sum);
}
}
printf("%d", ans);
return 0;
}
/**
14 8
11101010110011
*/