AcWing 3493. 最大的和(双指针)

Love The Way You Lie 2024-05-08 06:26 9阅读 0赞

##### 题目 #####

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

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

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

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

输入格式  
第一行包含两个整数 n 和 k。

第二行包含 n 个整数 ai。

第三行包含一个长度为 n 的 01 序列，如果第 i 个数为 1，表示 ai 的初始状态为可选，如果第 i 个数为 0，表示 ai 的初始状态为不可选。

输出格式  
一行一个整数，表示答案。

数据范围  
对于 30% 的数据，1≤k≤n≤1000  
对于 100% 的数据，1≤k≤n≤105,1≤ai≤105  
输入样例1：

3 1
    2 5 4
    0 0 1

输出样例1：

输入样例2：

4 3
    10 5 4 7
    0 1 1 0

输出样例2：

##### 思路 #####

题目要求找到一个连续的区间，使得将区间内元素全部置为可选状态后，整个数组可选元素和最大。  
最终的可选元素数组和可分为两部分，一部分是原来本来就可选的，另一部分是经过变换后的由不可选变为可选的元素，这两个部分可以分开计算，首先计算本来就可选元素的总和，然后用一个双指针来依次进行遍历，找出最大值。

##### 代码 #####

#include <iostream>
    
    using namespace std;
    
    typedef long long LL;
    
    const int N = 100010;
    
    int a[N], b[N];
    int n, k;
    
    int main() {
        
        scanf("%d%d", &n, &k);
        for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
        for(int i = 0; i < n; i ++) scanf("%d", &b[i]);
        //先求出所有可选的元素之和
        LL s = 0;
        for(int i = 0; i < n; i ++) {
        
            if(b[i]) s += a[i];
        }
        //
        LL v = 0, cur = 0;
        //j代表滑动窗口的右端
        for(int j = 0; j < n; j ++) {
        
            //如果滑动窗口右端点不可选，则需要加上
            if(!b[j]) cur += a[j];
            //如果滑动窗口左端点的前一个元素状态为不可选，则需要减去，因为上一次已经选过了
            if(j >= k && !b[j - k]) cur -= a[j - k];
            v = max(v, cur);
        }
        printf("%lld\n", s + v);
        return 0;
    }