AcWing 3493. 最大的和 超简洁的滑动窗口O(n)
原题链接
简单
作者:
蓬蒿人阿
,
2021-05-11 20:46:22
,
所有人可见
,
阅读 229
简洁的滑动窗口 O(n)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int a[N] , b[N] , n , k ; // a(数列) b(状态序列)
long long presum , temp , area; // presum(可选状态总和)
// temp(当前窗口不可选状态和)
// area(窗口和的最大值)
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> k ;
for(int i = 0 ; i < n ; i++) cin >> a[i]; // 读入数列
for(int i = 0 ; i < n ; i++) cin >> b[i]; // 读入状态序列
for(int i = 0 ; i < n ; i++){ // 一趟遍历
if(b[i]) presum += a[i]; // 可选时 直接加入presum
else temp += a[i];
if(i >= k && !b[i-k]) temp -= a[i-k]; // 当窗口大小大于等于k后 如果第i-k个数原本为不可选状态
// 滑动窗口要将第i-k个排除
area = max(area,temp); // 在当前窗口和最大窗口中选最大值
}
cout << presum + area << endl;
return 0;
}