题目

题目地址

给定一个长度为 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≤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

思路

首先是暴力思想，遍历所有K区间，将所有可能列出，选择最大的即可，对于小量数据确实可以做到，但大数据就不能达到要求，那么就需要在暴力的基础上进行优化。

我们可以把k区间看作一个滑动窗口，依次向右移动，每一次移动，左边的出去，右边的进来，我们可以用一个变量来记录当前区间相关的值，也就是把0换成1可以增加的数值，当移动时，最左边的出去，如果其是0，那么就需要减去最左边的数值，因为他已经出去了，我们此时的K区间不包含它，相反是1就不要变化，因为它不需要改变。这样我们可以用两个指针来记录区间的左端点和右端点，依次向右移动，只需要遍历一遍即可，便可以找到最大的增加值。

代码

#include<iostream>
using namespace std;
int n, k;
int const N = 1e5 + 10;
int a[N];
bool b[N];
typedef long long ll;
int main() {
	cin >> n >> k;;
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	ll s = 0;
	for(int i = 0; i < n; i++) {
		cin >> b[i];
		if(b[i]) s += a[i];
	}
	ll z = 0;
	for(int i = 0; i < k; i++) 
		if(!b[i]) z+= a[i];
	ll t = z;
	int i = 0, j = k;
	while(j < n) {
		if(!b[i]) z -= a[i];
		if(!b[j]) z += a[j];
		i++, j++;
		t = max(t, z);
	}
	s += t;
	cout << s << endl;
	return 0;
}