面灵AI→

上海 AI Lab 11 月 7 日机考:限额窗口清零与冷链运输预测

轮次
笔试
时间
2026-11
来源
牛客网

《面试题目》

第 1 题 — 限额窗口清零

某监控系统会对一串读数做定长片段抽检:每次必须截取恰好 W 个相邻读数作为一个片段来评估。现给出长度为 N 的非负整数序列 b、一个阈值 L 以及片段长度 W。

选好一个长度恰为 W 的连续片段后,允许把片段里最多一个读数改写成 0,也可以一个都不改。把处理后片段内所有读数相加得到 S,要求 S ≤ L。请在所有满足要求的片段与改写方式中,求出 S 能取到的最大值;如果任何片段无论怎样处理都无法满足 S ≤ L,输出 0。

输入描述:本题有多组测试数据。第一行是一个整数 Q,表示测试数据的组数。每组数据占两行:第一行三个整数 N, L, W,依次表示序列长度、阈值和片段长度;第二行 N 个整数 b₁, b₂, …, b_N,表示序列中的读数。

数据范围:1 ≤ Q ≤ 2×10⁵;1 ≤ W ≤ N ≤ 2×10⁵;0 ≤ L ≤ 10⁹;0 ≤ b_i ≤ 10⁹;同一个测试文件中所有 N 之和不超过 5×10⁵。

输出描述:每组数据输出一行一个整数,表示满足 S ≤ L 时 S 的最大值;不存在合法方案时输出 0。

样例输入:

3
5 9 2
3 6 2 7 4
6 9 3
5 1 6 3 3 8
3 1 2
4 6 5

样例输出:

9
9
0

样例说明:

  1. 第 1 组:片段 [3,6] 的和恰好为 9,不用改写即可,答案 9。
  2. 第 2 组:片段 [1,6,3] 的和为 10,超出阈值 1,把其中的 1 改成 0 后和为 9;若只想着把最大值 6 清零,只能得到 4。其他片段也凑不出比 9 更大的合法和,所以答案为 9。
  3. 第 3 组:每个片段改写任意一个读数后,剩下的那个读数至少是 4,都超过阈值 1,不存在合法方案,输出 0。

第 2 题 — 冷链物流货物安全运输

题目要求根据冷链运输过程中的实时数据,预测货……(原帖正文在牛客服务端即被截断于此,题面未完整保留)

《参考解析》

第 1 题:窗口和 + 窗口内有序集合。固定一个长度为 W 的片段,设当前和为 S:若 S ≤ L,不改写就是该片段的最优解;若 S > L,被清零的那个数 v 必须满足 S − v ≤ L,即 v ≥ S − L。v 越小结果越大,所以要在片段里找不小于 S − L 的最小数,找不到说明这个片段无论清零哪个数都超限。用滑动窗口枚举全部 N − W + 1 个片段,右移时插入一个、删除一个,并在有序集合上查一次下界。C++ 用 multiset 配 lower_bound;Java 用 TreeMap 记次数、ceilingKey 查询(同一数值可能重复出现,只存一份会漏掉窗口里的重数);Python 标准库没有有序集合,用分块有序表代替——块内用 bisect.insort 维护有序、块间有序,插入时定位到第一个末尾不小于 x 的块,块长超过 2 倍阈值就分裂,删除时在目标块内二分后弹出。所有片段取最大值,全部无解时输出 0。

边界与规模。b_i 与 L 都到 10⁹,单个片段的和最大约 10⁹ × 2×10⁵ = 2×10¹⁴,必须用 64 位整数,32 位会溢出成负数并被误判为「不超过 L」。Q 可以到 2×10⁵ 而所有 N 之和只有 5×10⁵,说明大部分组是小数据,读入要用快速输入(scanf 或自写 FastScanner),cin 不解除同步会拖慢。时间复杂度 O(N log N),Python 分块版 O(N√W);空间 O(W)。

第 2 题的方向。题面虽被截断,从标题看是根据冷链运输的实时数据(温度、湿度、开门次数、里程等传感器序列)预测货物是否仍安全,属于典型的多变量时序分类 / 预警建模:先做缺失值与异常值处理、按运输批次切分样本避免同一订单跨集合泄漏,再抽取滑窗统计特征(均值、极值、超阈值时长、波动率)接入树模型或时序网络,最后用「提前预警时间」和「误报率」两个指标评估,而不是只看准确率。

这次的取数限制。牛客只保留了该帖的前半段,第二题只剩题名;机考复盘帖若被平台截断,能复用的就是完整保留的那部分题面与解法。