题目描述
给定一个长度为 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
题目解读:求所有可选数据的和,我们可以设置一段区间全部为可选数据.
也就是要选出,给定长度内最大的不可选数据的和。使用双指针
区间长度为k,往后移动.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
//读入所需的数据
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();
int[] arr=new int[n];//数据值
int[] arr2=new int[n];//判断上面数据是否可选的数组
for(int i=0;i<arr.length;i++)
{
arr[i]=sc.nextInt();
}
for (int i = 0; i < arr2.length; i++) {
arr2[i]=sc.nextInt();
}
long sum=0;//没有变换时,所有可选数据的和
long max=0;
long ans=0;
//求和:
for(int i=0;i<n;i++)
{
if(arr2[i]==1)
{
sum+=arr[i];
}
}
//双指针往后移动
//往后移动前,第一个数据如果是我们改为可选的,需要减去
//往后移动以后,最后一个数据如果是不可选,把它设置为可选,再加入的当前可选数据和ans中
for (int i = 0; i < n; i++) {
if(arr2[i]==0)
{
ans+=arr[i];
}
if(i>=k && arr2[i-k]==0)
{
ans-=arr[i-k];
}
max=Math.max(ans,max);
}
System.out.println(max+sum);
}
}