题目描述
给定一个长度为 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:
9
输入样例2:
4 3
10 5 4 7
0 1 1 0
输出样例2:
19
难度:简单
时/空限制:1s / 256MB
总通过数:610
总尝试数:1544
来源:贝壳找房2021,笔试题
算法标签
双指针前缀和
算法1
(双指针) O(n)
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], s[N];
int n, k;
int main()
{
ios::sync_with_stdio(false);
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
LL sum = 0;
//固定好指针的位置
int l = 0;
int r = k - 1;
//初始化
for (int i = 0; i < n; i++)
{
cin >> s[i];
if (s[i] == 1)
{
//把数列里面可选的都拿来
sum += a[i];
}
if (i <= r && s[i] == 0)
{
//把一开始两个指针范围里面的数都拿来
sum += a[i];
}
}
LL res = sum;
//cout << res << endl;
//指针开始往右边走
while (++r < n)
{
//左边踢出去,右边放进来,更新sum
//l是0要减,l是1不动,r是0要加,r是1不动
if(s[r] == 0){
sum += a[r];
}
if(s[l] == 0){
sum -= a[l];
}
//看一下谁大,更新一下
res = max(res, sum);
//把最左边的踢走
l++;
}
cout << res;
}