双指针题目

感谢谢Herself32 dalao 的讲解

luogu题目地址

codeforces题目地址

题目描述

C. Hard Process

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

You are given an array a with n elements. Each element of a is either $0$ or $1$.

Let's denote the length of the longest subsegment of consecutive elements in $a$, consisting of only numbers one, as $f(a)$. You can change no more than $k$ zeroes to ones to maximize $f(a)$.

Input
The first line contains two integers $n$ and $k (1 \leq n \leq 3·10^5, 0 \leq k \leq n)$ — the number of elements in $a$ and the parameter $k$.

The second line contains $n$ integers $a_i (0 \leq a_i \leq 1)$ — the elements of $a$.

Output
On the first line print a non-negative integer $z$ — the maximal value of $f(a)$ after no more than k changes of zeroes to ones.

On the second line print $n$ integers $a_j$ — the elements of the array $a$ after the changes.

If there are multiple answers, you can print any one of them.

题解

假做法1

我们发现我们把$k$次机会全部使用完是最佳决策。

于是我们只需暴力枚举一个左端点$l$和一个右端点$r$，统计他们中间的$0$的个数。
复杂度$O(n^3)$

假做法2

前缀和优化一下。

时间复杂度$O(n^2)$。

正解

我们用双指针解这题，我们首先定义一个$l$和$r$，和假做法1一样，我们需要统计$0$的个数，我们能够更新答案的时候，当且仅当$0$的个数$\leq k$，如果条件成立，我们把$r++$之后再次进行判断，否则缩小区间，令$l++$便可。

Code

卡了常，代码可读性会有些差。

#include <cstdio>
#define maxn 300005

int a[maxn];
int n, k;

int main ()
{
    register int l = 1, r = 1, cnt = 0, qwq, ans = 0, L, R;      //小变量放到寄存器里
    scanf ("%d%d", &n, &k);
    for (register int i = 1; i <= n; ++i)
    {
        getchar ();              //因为是 0 1， 所以快读常数比getchar大 ，不用写快读啦
        a[i] = getchar () - '0';
    }

    while (r <= n)
    {
        cnt += !a[r];      //统计0的个数
        if (cnt > k)
        {
            cnt -= !a[l];
            ++l;
        }
        qwq = r - l + 1;   //临时变量，减少计算次数
        if (qwq > ans)    //杜绝MAX 减少赋值次数
        {
            ans = qwq;
            L = l;
            R = r;
        }
        ++r;
    }

    printf ("%d\n", ans);

    for (register int i = L; i <= R; i++) a[i] = true;

    for (register int i = 1; i <= n; i++)
    {
        putchar (a[i] + '0');
        putchar (' ');
    }

    return 0;
}

于是成功在2019.10.21卡到luogu最优解第一页

THE END