解题思路
小明要在长度为 k 的连续区间里,让“舒适度总和”尽可能大;若最大值有多段并列,取最靠前的一段。因 k 为奇数,区间存在唯一的居中位置,设区间左端为 L,则居中位置为 L+⌊k/2⌋。
核心就是在数组上寻找固定长度为 k 的最大子段和。这正是典型的滑动窗口问题:
- 先计算前 k 个元素的和作为当前窗口和;
- 之后每次窗口右移 1 格:从窗口和中减去离开的元素,加入新进入的元素;
- 同步维护最大和与其对应的最左窗口左端位置。若出现相等的最大和,不更新(保持更靠前的那一段)。
P3592.第2题-选住址
题目内容
小明搬到了一个新的城市,第一件事当然就是为自己选一个合适的住址。
现在他已经选定了一条街道,准备在街道的某个位置住下来。小明给每个位置赋值了一个舒适度。
他希望选出一个连续长度为 k 的区间,其舒适度之和是所有可选方案中的最大值。
然后小明将在居中的位置住下来。如果达到最大值的区域有多个,小明会选择前的一个(保证 k 为奇数,即一定存在居中的位置)
你的任务是求出这个位置在何处。
输入描述
第一行两个正整数 n,k(1<=n,k<=100000) ,分别表示街道的长度,小明想要考虑的连续长度 k
第二行 n 个正整数,以空格分隔。表示小明认为的每个位置的舒适度,每个位置的舒适度位于 [1,10000] 之间。
输出描述
输出小明选定的家的住址位置。
样例1
输入
10 3
5 5 5 10 10 10 5 10 10 10
输出
5