3493. 最大的和 (滑动窗口)
3493. 最大的和 (滑动窗口)
浪漫主义狗
发布于 2022-07-11 08:53:06
发布于 2022-07-11 08:53:06
3493. 最大的和 (滑动窗口)
描述
给定一个长度为 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分析
- 该题目可将最大和分为两部分，即为可用状态的和
sum以及选定区间内不可用状态的最大的和s - 以选定区间的长度作为窗口，每次向右滑动，加上右边界状态为
0的数，减去左边界状态为0的数，维护一个最大值 - 循环遍历先求
sum，再循环遍历窗口得到最大和，两者相加即为答案
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int a[N],b[N]; //a用于存放数，b用于存放状态
int main(){
int n,k;
cin>>n>>k;
ll sum=0,v=0,s=0; //sum为状态是1的数的和，v为窗口内改变状态后最大的和，s计算当前窗口的和
for(int i=0;i<n;i++) scanf("%d",&a[i]); //初始化a
for(int i=0;i<n;i++){
scanf("%d",&b[i]); //初始化b
if(b[i]) sum+=a[i]; //计算sum
}
for(int i=0;i<n;i++){
if(b[i]==0) s+=a[i]; //如果该数状态为0，则视其状态改变并加上该数
if(i>=k&&b[i-k]==0) s-=a[i-k]; //当i大于等于k时，窗口开始向右滑动，每次滑动减去左边界状态为0的数
v=max(v,s); //维护窗口最大和
}
printf("%lld",sum+v);
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-6-15 8，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录