题目描述
给定一个长度为 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
算法
滑动窗口
- 状态为1的肯定是在可选状态总和里面,先将状态为1的所有相加 ,再寻找状态为0的
- 由于题目有给定的k,则可以使用滑动窗口,k为滑动窗口长度
- 当窗口往前移时,添加状态为0的
- 当窗口往前移并且超过规定长度,则将窗口后面的减去
- 每次统计当前窗口的总和
- 答案就是 窗口的最大值,状态为1的和
java 代码
import java.util.*;
class Main{
static int N = 100010;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[N];
int[] b = new int[N];
for(int i = 0 ;i < n ; i++){
a[i] = sc.nextInt();
}
for(int i = 0 ;i < n; i++){
b[i] = sc.nextInt();
}
long sum = 0;
//循环 把状态为1的都计算进去
for(int i = 0; i < n ; i++){
if(b[i]==1){sum+=a[i];}
}
long v = 0, s = 0;
for(int i = 0 ; i < n ;i ++){
//滑动窗口,如果为不可选中 则先加入到s中
if(b[i]==0){s+=a[i];}
//i一定要大于等于m, 当m为2时 说明前两个如果b都为0则直接加入,那么就有s里面就有两个了
//i>=m开始判断 滑动窗口里面的数量
//&&后面就是 判断滑动窗口前面是否状态为0,如果为0 则减去 ,因为i>=m窗口已经超出长度了
if(i>=m && b[i-m]==0){
s -= a[i-m];
}
//每次判断一下获得数值最大的,存入v中
v = Math.max(v,s);
}
System.out.print(sum+v);
}
}
兄弟有时间填个邀请码hhhhhhhhh(可以得AC币,邀请码在学生认证那填) 我的邀请码是:GUDFH