贝壳找房 · 滑动窗口 · 算法编程题
贝壳找房 滑动窗口 n ≤ 1e5 时限 1 秒 / 256 MB

题目描述

S星球由 n 个国家组成,每个国家的实力为 a_i .
小明提出了结盟的想法,但每个国家的想法不一,有的同意结盟,有的不同意结盟.
因为小明的国际实力,他可以选择一个长度为 k 的区间 [i,i+k-1](1≤ i ≤ n+1-k) ,并让区间内的国家强行同意结盟.
小明想问问你结盟国家的实力和最大是多少.

输入输出

输入描述
第一行两个整数 n,k ,表示国家数和小明可以说服的区间长度 (1≤ k ≤ n ≤ 1e5)
第二行 n 个整数 a_i ,表示第 i 个国家的实力 (1≤ a_i ≤ 1e5)
第三行 n 个整数 b_i ,表示第i个国家是否支持结盟,如果 b_i =1 则表示支持,反之不支持 (0≤ b_i ≤ 1)
输出描述
一个整数,保证结果.

样例共 3 组

样例 1 · 小明选择让区间[2,2]即实力为5的这个国家强行同意结盟，故有结盟意向的国家总共为9 = 5 + 4
输入
3 1
2 5 4
0 0 1
输出
9
样例 2 · 小明选择让区间[1,3]这些国家强行同意结盟，故有结盟意向的国家总共为9 = 10+5+4
输入
4 3
10 5 4 7
0 1 1 0
输出
19
样例 3 · 小明选择让区间[1,2]这些国家强行同意结盟，故有结盟意向的国家总共为1+1+3+3=8
输入
4 2
1 1 3 3
0 0 1 1
输出
8

算法解析依据充分

考点：滑动窗口

数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：k ≤ 1e5，n ≤ 1e5
  • 元素值域：a_i ≤ 1e5（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：滑动窗口

本题切入点

长度为 k 的区间实力和最大，先累加支持结盟的实力和，再用滑动窗口枚举被强行说服的区间带来的增量。

维护一个连续区间，进一个元素出一个元素，区间内统计量增量更新。

思路框架（滑动窗口 通法 · 非本题专属）

  1. 用左右指针确定一个窗口 [l, r]。
  2. 右端点右移：把新元素加入窗口统计。
  3. 当窗口违反约束（长度超限 / 含重复等）时，左端点右移，把元素移出统计。
  4. 在每个合法窗口上更新答案。
  5. 统计量用哈希表或计数数组维护，避免每次重算。

实现要点：注意窗口长度是定长还是不定长：定长则区间长度固定为 k，不定长则靠条件收缩。

复杂度：时间 O(n) ｜ 空间 O(字符集/去重元素数)

该范式的通法易错点

  • 移出窗口时忘同步更新统计量。
  • 窗口长度与下标边界差 1（长度 k 对应 r-l+1）。

对照本题

  • 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 元素值域最大到 1e5 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 1 / 2 5 4 / 0 0 1 → 输出 9

小明选择让区间[2,2]即实力为5的这个国家强行同意结盟，故有结盟意向的国家总共为9 = 5 + 4

样例 2：输入 4 3 / 10 5 4 7 / 0 1 1 0 → 输出 19

小明选择让区间[1,3]这些国家强行同意结盟，故有结盟意向的国家总共为9 = 10+5+4

样例 3：输入 4 2 / 1 1 3 3 / 0 0 1 1 → 输出 8

小明选择让区间[1,2]这些国家强行同意结盟，故有结盟意向的国家总共为1+1+3+3=8

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：【2023】贝壳找房春招前端工程师笔试卷2；【2023】贝壳找房春招测试开发工程师笔试卷2。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解