1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

解题思路

小明要在长度为 kkk 的连续区间里,让“舒适度总和”尽可能大;若最大值有多段并列,取最靠前的一段。因 kkk 为奇数,区间存在唯一的居中位置,设区间左端为 LLL,则居中位置为 L+⌊k/2⌋L+\lfloor k/2 \rfloorL+⌊k/2⌋。

核心就是在数组上寻找固定长度为 kkk 的最大子段和。这正是典型的滑动窗口问题:

  • 先计算前 kkk 个元素的和作为当前窗口和;
  • 之后每次窗口右移 1 格:从窗口和中减去离开的元素,加入新进入的元素;
  • 同步维护最大和与其对应的最左窗口左端位置。若出现相等的最大和,不更新(保持更靠前的那一段)。

P3592.第2题-选住址

    1000ms Tried: 75 Accepted: 28 Difficulty: 3 所属公司 : 得物
    算法与标签>前缀和

题目内容

小明搬到了一个新的城市,第一件事当然就是为自己选一个合适的住址。

现在他已经选定了一条街道,准备在街道的某个位置住下来。小明给每个位置赋值了一个舒适度。

他希望选出一个连续长度为 kkk 的区间,其舒适度之和是所有可选方案中的最大值。

然后小明将在居中的位置住下来。如果达到最大值的区域有多个,小明会选择前的一个(保证 kkk 为奇数,即一定存在居中的位置)

你的任务是求出这个位置在何处。

输入描述

第一行两个正整数 n,k(1<=n,k<=100000)n,k(1<= n,k<= 100000)n,k(1<=n,k<=100000) ,分别表示街道的长度,小明想要考虑的连续长度 kkk

第二行 nnn 个正整数,以空格分隔。表示小明认为的每个位置的舒适度,每个位置的舒适度位于 [1,10000][1,10000][1,10000] 之间。

输出描述

输出小明选定的家的住址位置。

样例1

输入

10 3
5 5 5 10 10 10 5 10 10 10

输出

5

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 1, 31ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?