题目描述

双指针

类似模板题：最长连续不重复子序列
https://www.acwing.com/solution/content/230806/

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = 300010;
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] w = new int[N];

        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
        }

        //len表示最长子串1的长度，r为最长子串1的长度的右边界
        int len = 0, r = 0;
        for (int i = 0, j = 0, zeros = 0; i < n; i++) {
            //次数加1
            if (w[i] == 0) zeros++;
            //如果大于大于能改变的次数
            while (zeros > m) {
                //把是0的退出，次数-1
                if (w[j] == 0) zeros--;
                //尾指针++
                j++;
            }
            //t为当前字串的长度
            int t = i - j + 1;
            //如果当前字串的长度大于len 更新len和r
            if (t > len) {
                len = t;
                r = i;
            }
        }

        System.out.println(len);
        //把r至r-len+1全变为1 
        for (int i = r; i > r - len; i--) w[i] = 1;
        for (int i = 0; i < n; i++) System.out.print(w[i] + " ");
    }
}

二分加前缀和

import java.util.Scanner;

public class Main {
    static final int N = 300010;
    static int[] a = new int[N];
    static int[] b = new int[N];

    static boolean check(int mid, int n, int k) {
        for (int i = n; i - mid + 1 >= 1; i--) {
            //要大于等于mid
            if (a[i] - a[i - mid] + k >= mid)
                return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
            b[i] = a[i];
            a[i] += a[i - 1];
        }
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid, n, k)) l = mid;
            else r = mid - 1;
        }
        System.out.println(l);
        int i;
        for (i = n; i - l + 1 >= 1; i--) {
            //这里也是大于等于mid
            if (a[i] - a[i - l] + k >= l) break;
        }
        //把i至i - j + 1全部变为1
        for (int j = 1; j <= l; j++) {
            b[i - j + 1] = 1;
        }
        for (int j = 1; j <= n; j++) {
            System.out.print(b[j] + " ");
        }
    }
}