题目描述
有一个长为 的字符串 ,只含 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
*/