【5.11】AcWing夏季·最大的和

2021年05月11日 19时59分

标签：滑动窗口

# 【5.11】AcWing夏季·最大的和

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

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

你可以选择一个长度恰好为 k 的区间 [i, i+k−1]，使得`a_i - a_{i+k−1}`这$$k$$个元素的状态全部变为可选。

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

#### 输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数 ai。

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

#### 输出格式

一行一个整数，表示答案。

#### 数据范围

```
对于 30% 的数据，1≤k≤n≤1000
对于 100% 的数据，1≤k≤n≤10^5,1≤ai≤10^5
```

#### 输入样例1

```
3 1
2 5 4
0 0 1
```

#### 输出样例1

```
9
```

#### 输入样例2

```
4 3
10 5 4 7
0 1 1 0
```

#### 输出样例2

```
19
```

#### 来源

> 来源：AcWing 3493
> 链接：[3493. 最大的和 - AcWing题库](https://www.acwing.com/problem/content/3496/)

## 解题思路

滑动窗口，贪心地选择窗口内不可选数字之和最大的窗口，将其中的所有数字置为可选即可。

注意，代码中记录滑动窗口位置的变量`pos`，记录的是滑动窗口的右边界而不是左边界，调了40分钟才发现这个bug，😭

在限时的条件下，比较难集中注意力思考，日后需要锻炼。

## 代码

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
int a[N];
int avail[N];

int main(void){
    int n, k;
    
    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", &avail[i]);
    }
    
    long long sum = 0;
    long long maxn = 0, pos = k-1;
    
    for(int i = 0; i < k; i++){
        if(!avail[i]){
            sum += a[i];
        }
    }
    
    maxn = sum;
    pos = k - 1;
    for(int i = k; i <= n; i++){
        if(!avail[i-k]){
            sum -= a[i-k];
        }   
        if(!avail[i]){
            sum += a[i];
        }
        if(sum > maxn){
            maxn = sum;
            pos = i;
        }
    }
    
    long long res = 0;
    for(int i = 0; i < n; i++){
        if(avail[i] || (!avail[i] && i >= pos - k + 1&& i <= pos)){
            res += a[i];
        }   
    }
    
    printf("%lld\n", res);
    return 0;
}
```

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【5.11】AcWing夏季·最大的和

所有评论

暂无评论

新增评论