01反转

佚名 / 2023-08-23 / 原文

题目描述

有一个长为的字符串，只含 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
 */