题目描述
给定一个长度为 n 的正整数数列 a1,a2,…,an。
初始时,数列中的每个元素要么处于可选状态,要么处于不可选状态。
你可以选择一个长度恰好为 k 的区间 [i,i+k−1],使得 ai∼ai+k−1 这 k 个元素的状态全部变为可选。
请问,在经过此操作后,所有处于可选状态的元素之和最大是多少。
样例
输入样例
4 3
10 5 4 7
0 1 1 0
输出样例
19
数据范围
对于 30% 的数据,1≤k≤n≤1000
对于 100% 的数据,1≤k≤n≤10^5,1≤ai≤10^5
算法一
前缀和 $O(n)$
根据题意,可以将所要求的和分为两部分, 第一部分是本来状态就是1的数的和, 用sum1表示, 第二部分是窗口k 内本来状态为0, 后被置为1的数的和, 使用sum2表示, 则最终答案为这两者之和;
因为窗口可以看作一个区间, 于是这里先用前缀和做一遍;
使用前缀和数组的时候, 前缀和数组中存的是状态为0的数的前缀和, 所有状态为1的数不被计入前缀和数组中;
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e5+7;
typedef long long LL;
int a[N]; //保存原数组;
LL s[N], sum1; //状态0的前缀和数组与 状态1的所有数之和;
int main()
{
ios::sync_with_stdio(false);
int n, k;
cin>>n>>k;
for(int i = 1; i <= n; ++i)
cin>>a[i];
for(int i = 1; i <= n; ++i){
int b;
cin>>b;
if(b == 0) //状态为0时计入前缀和数组中;
s[i] = s[i-1] + a[i];
else{
s[i] = s[i-1]; //状态为1的数不计入前缀和;
sum1 += a[i]; //但是加到sum1中;
}
}
LL sum2 = 0;
for(int i = 0; i < n-k+1; ++i){ //找到窗口为k的区间里状态0的数之和最大值, 使用sum2保存;
if(s[i+k] - s[i] > sum2)
sum2 = s[i + k] - s[i];
}
cout<<sum2 + sum1; //最终答案即为这两部分数之和
return 0;
}
算法2
滑动窗口 $O(n)$
如上所述, sum2为一个窗口内的状态为0的数之和, 则可以使用滑动窗口来做
C++代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+7;
typedef long long LL;
int a[N], b[N]; //a为数据数组,b为状态数组;
LL sum1, sum2;
int main()
{
ios::sync_with_stdio(false);
int n, k;
cin>>n>>k;
for(int i = 1; i <= n; ++i)
cin>>a[i];
for(int i = 1; i <= n; ++i){
cin>>b[i];
if(b[i])
sum1 += a[i]; //输入状态数组的同时把sum1算出来;
}
LL tmp = 0;
for(int i = 1; i <= n; ++i){
if(!b[i]) tmp += a[i]; //滑动窗口右边界, 状态为0就加到临时变量里;
if(i > k && !b[i-k]) tmp -= a[i-k]; //滑动窗口左边界, 超出窗口长度且状态为0就减去;
sum2 = max(sum2, tmp);
}
cout<<sum2 + sum1;
return 0;
}