3493. 最大的和 (滑动窗口)
本文最后更新于 874 天前,其中的信息可能已经有所发展或是发生改变。

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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇