题目描述

给定一个长度为 n 的正整数数列 a1,a2,…,an。

初始时，数列中的每个元素要么处于可选状态，要么处于不可选状态。

你可以选择一个长度恰好为 k 的区间 [i,i+k−1]，使得 ai∼ai+k−1 这 k 个元素的状态全部变为可选。

请问，在经过此操作后，所有处于可选状态的元素之和最大是多少。

样例

3 1
2 5 4
0 0 1

9

算法1

(双指针) $O(n)$

先求第一段长度为k里不可选的值，然后循环，如果前一个不可选就减去，后一个不可选就加上，不断与当前最大值比较找出最大，最后加上所有可选的

C++ 代码

#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
    scanf("%d",&b[i]); //输入结束

    long long int d=0; //必须开long long,不然k比较大的时候会爆int
    for(int i=0;i<k;i++)
        if(!b[i]) d+=a[i]; //求第一段长度为k里不可选的值

    long long int res=d; //也开long long,k大了会爆int
    for(int i=0,j=k;j<n;i++,j++) //i指向每一段k内的第一个值，j指向每一段k的下一个值,
    {
        if(!b[i]) d-=a[i]; //i指向的值不可选就减去
        if(!b[j]) d+=a[j]; //j指向的值不可选就加上
        res=max(res,d); //找最大值
    }
    for(int i=0;i<n;i++)
        if(b[i]) res+=a[i]; //累加所有可选值
    cout<<res;
    return 0;
}

算法2

(前缀和) $O(n)$

求不可选的前缀和，然后算每一段k范围内的前缀和值，与最大值比较，加上可选的输出就好，总体思路与双指针是一样的

C++ 代码

#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
long long c[N]; //存前缀和，开long long，防止爆int 
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);

    long long d=0,res=0; 
    for(int i=1;i<=n;i++)
    {
        c[i]=c[i-1]; //先把上一个前缀和copy过来
        if(!b[i]) c[i]+=a[i]; //如果这个不可选就加上，可选就不用管
        if(b[i]) d+=a[i]; //累加可选值
        if(i>=k) res=max(res,c[i]-c[i-k]); //找最大值
    }
    cout<<res+d; 
    return 0;
}