← 返回编程题库
coding-min-window-size-meet-volume-target中等免费版2000ms未尝试

满足每个窗口都达到目标成交量的最小切片长度

Smallest Slice Length Whose Every Window Meets a Volume Target

开始编码

实现 solution(volumes: list[int], Q: int) -> int。某执行台运行被动子单计划,把订单切到 N 个等长时段上,每个时段的成交量由数组 volumes 给出(每项为非负整数)。该执行台希望承诺单一固定切片长度 W,使得每一个长度为 W 的连续切片都承载足够的成交量来吸收一笔子单——形式化地说,返回最小的整数 W ∈ [1, N] 使得 min over i in [0, N-W] of sum(volumes[i:i+W]) >= Q。若 Q <= 0,返回 1(任意切片都已满足非正目标);若 N == 0Q > 0,或者连 W = N 的整窗和都低于 Q,则返回 -1

solution([5, 5, 5, 1, 5, 5, 5, 5], 6) 返回 2W = 1 时最小窗口和 = 1(那个唯一收紧的时段),低于目标 6,不可行;W = 2 时窗口 (1, 5) 的和恰为 6,其他长度 2 窗口的和均为 10,最小值为 6 >= 6——可行。故 2 是每个窗口都能吸收至少 Q = 6 单位的最小切片长度。solution([4, 4, 4, 4, 4], 13) 返回 4:常数 volumes 时每个长度 W 的窗口和 = 4 * W4 * 3 = 12 < 134 * 4 = 16 >= 13solution([1, 1, 1, 1, 1], 100) 返回 -1,因为整段总和 5 < 100

关键形态是在 [1, N] 上**对答案 W 二分**:因为 volumes 非负,扩张窗口只会增和,所以「最小窗口和」关于 W 非减。先派发不可行分支(sum(volumes) < Q)和平凡分支(Q <= 0),然后用 O(N) 的前缀和可行性判定做每步二分。从 1 起对 W 做线性扫描的成本是 O(N^2),在输入上界会 TLE。

函数骨架见 stubs/stub.py

实践背景

一个被动执行台已经把母单切到逐时段子单计划上,希望知道最短的切片长度,能保证任意一段该长度的连续切片都承载足够的成交量来完整吸收每段子单数量 Q。盘前分析层给出每时段的成交量预测 volumes[i],即在该场所典型微观结构状态、当日 ADV 缩放与执行台挂单档位下,时段 i 的预期总成交量。任何承载量低于 Q 的切片都会带来排队位置衰减与该段缺单的风险,所以执行台关心的是当天最差(最小)的那一段,而非平均段。每个长度 W 窗口都达到 Q 的最小 W,就是当日计划的切片长度参数。如果连整窗都达不到 Q,说明在该场所、该规模上计划本身不可行,执行台需要升级处理——这就是 -1 的语义。

约束条件

  • 0 <= N <= 200_000,其中 N = len(volumes);volumes[i] 是非负整数,volumes[i] <= 10^9
  • 0 <= Q <= 10^18(Q 为整数);按合约 Q <= 0 时返回 1
  • 若 N == 0 且 Q > 0 返回 -1;若 sum(volumes) < Q 返回 -1;否则返回最小的整数 W ∈ [1, N],使得 volumes 的每个长度为 W 的连续窗口之和 >= Q
  • 输出为单个 int;比较器为 exact
  • 参考解复杂度:时间 O(N log N),空间 O(N)(前缀和)

样例

Case 1 · statement-example: single tight minute drives W up

输入: [[5,5,5,1,5,5,5,5],6]

期望: 2

length-1 窗口最小和 = 1 < 6 不行;长度 2 时窗口 (1,5) 和 = 6 满足,且其他长度 2 窗口和 >= 10。最小 W = 2。

Case 2 · statement-example: uniform volumes give ceil(Q/v)

输入: [[4,4,4,4,4],13]

期望: 4

常数 4 序列,目标 13;W=3 时每窗口和 = 12 < 13,W=4 时每窗口和 = 16 >= 13,最小 W = 4。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · statement-example: single tight minute drives W up

输入: [[5,5,5,1,5,5,5,5],6]

期望: 2

length-1 窗口最小和 = 1 < 6 不行;长度 2 时窗口 (1,5) 和 = 6 满足,且其他长度 2 窗口和 >= 10。最小 W = 2。

Case 2 · statement-example: uniform volumes give ceil(Q/v)

输入: [[4,4,4,4,4],13]

期望: 4

常数 4 序列,目标 13;W=3 时每窗口和 = 12 < 13,W=4 时每窗口和 = 16 >= 13,最小 W = 4。