双指针-CF660C题解

发布于 2019-10-22  278 次阅读


双指针题目

感谢谢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