最少撤单次数维持报价稳定
Min Cancels for Quote Stability
开始编码做市台对每个标的挂一张双边报价:以一个 anchor 价 a 为锚,bid = a − half_spread,ask = a + half_spread。然后市场中价(fair value)会一路漂——随着 fairs[0], fairs[1], … 一个个 tick 刷新,已经挂在簿上的这张报价不动,但离 fair 较近的那一边的有效报价距离会随漂移压缩。具体地说:如果 fair 当前是 f,那靠近 fair 那一边的有效距离就是 half_spread − |f − a|。做市风控线划在「这条有效距离不能小于 min_spread」上——一旦压不住,就必须撤单、按当前 fair 重新挂一张新的报价。
请实现 solution(fairs: list[float], half_spread: float, min_spread: float) -> int,返回最少需要挂多少张报价才能把整段 fairs 走完(包括首次挂的那一张)。fairs 为空时返回 0。
把约束翻译成几何关系:一张 anchor 价为 a 的报价能覆盖连续的 fairs[i..j],当且仅当存在 a 使得对所有 k ∈ [i, j]:|fairs[k] − a| ≤ D,其中 D = half_spread − min_spread。这等价于 max(fairs[i..j]) − min(fairs[i..j]) ≤ 2D(取 a = (max + min) / 2 时距离正好压到 D)。问题就退化成:把 fairs 切成最少的连续段,每段极差 ≤ 2D。这是教科书式的「区间分割贪心」——每段从当前位置贪心地往右扩到极限,再开新段。
举个例子:solution([100.00, 100.05, 100.20, 100.21], 0.10, 0.04) 应返回 2。D = 0.06、2D = 0.12。第一张报价从 fairs[0] = 100.00 开始挂,覆盖到 fairs[1] = 100.05 时极差 = 0.05,OK;到 fairs[2] = 100.20 时极差 = 0.20 > 0.12,必须撤单。第二张报价从 fairs[2] 开始,覆盖 fairs[2..3] 极差 = 0.01,撑到走完。共 2 次刷新。
注意三条边界:(1) min_spread > half_spread 时 D < 0,每个 tick 都撑不住,返回 n;(2) 越界判定要严格大于 2D,等于不算越界——这一点在浮点比较时加个 1e-12 量级的容差最稳;(3) 大数据量下用单调双端队列 O(n) 维护滑动 max/min,避免每次重算 max/min 退化成 O(n²)。
约束条件
- 0 ≤ len(fairs) ≤ 100000
- fairs[i] 是浮点数,|fairs[i]| ≤ 1e9
- half_spread > 0;min_spread ≥ 0;二者均为浮点
- 返回 int:最少刷新次数(首次挂单也算 1 次刷新);空 fairs 返回 0
- 时间复杂度 O(n),n = 1e5 时 O(n²) 在大用例上会超时
- 浮点边界判定允许 1e-9 量级容差:max − min == 2D 视为可行
样例
Case 1 · statement example: single drift triggers one refresh
输入: [[100,100.05,100.2,100.21],0.1,0.04]
期望: 2
half_spread=0.10、min_spread=0.04,所以 anchor 漂移上限 D = 0.06,单次报价能覆盖的 fair 区间宽度 ≤ 2D = 0.12。第 0 张报价在 fairs[0..1] 区间(max-min=0.05)撑得住,到 fairs[2]=100.20 时 max-min=0.20 已经超过 0.12,必须撤单重挂。新报价从 fairs[2] 开始,能撑到 fairs[3](max-min=0.01)。一共两次刷新。
Case 2 · tight band: every tick needs its own quote
输入: [[100,100.5,101,101.5],0.2,0.1]
期望: 4
D = 0.10,单次 quote 覆盖宽度 ≤ 0.20。相邻 fair 间隔 0.5 已经把单次报价挤到只能覆盖一个 tick,所以四个 tick 各自需要一次刷新,答案是 4。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement example: single drift triggers one refresh
输入: [[100,100.05,100.2,100.21],0.1,0.04]
期望: 2
half_spread=0.10、min_spread=0.04,所以 anchor 漂移上限 D = 0.06,单次报价能覆盖的 fair 区间宽度 ≤ 2D = 0.12。第 0 张报价在 fairs[0..1] 区间(max-min=0.05)撑得住,到 fairs[2]=100.20 时 max-min=0.20 已经超过 0.12,必须撤单重挂。新报价从 fairs[2] 开始,能撑到 fairs[3](max-min=0.01)。一共两次刷新。
Case 2 · tight band: every tick needs its own quote
输入: [[100,100.5,101,101.5],0.2,0.1]
期望: 4
D = 0.10,单次 quote 覆盖宽度 ≤ 0.20。相邻 fair 间隔 0.5 已经把单次报价挤到只能覆盖一个 tick,所以四个 tick 各自需要一次刷新,答案是 4。