第1题-最小化峰值干扰

小红书9月10日机考题目与解析

要将 $m$ 项探测任务按给定顺序安排到连续 $n$ 个时隙。第 $j$ 个时隙的干扰强度为 $a_j$，第 $i$ 项任务占用连续 $b_i$ 个时隙。记 $l_i$ 为第 $i$ 项任务的起始时隙，则其占用区间为 $[l_i,\ l_i + b_i - 1]$。

安排须满足：

1. 任务占用互不重叠：对任意 $i < j$，有 $l_i + b_i - 1 < l_j$；任务之间可空出任意个时隙。
2. 任务保持给定顺序：$l_1 < l_2 < \cdots < l_m$。
3. 均落在时隙范围内：$1 \le l_i$ 且 $l_i + b_i - 1 \le n$。

峰值干扰为

$$\max_{i=1}^{m}\ \max_{j=l_i}^{l_i + b_i - 1} a_j$$

求所有合法安排下峰值干扰的最小值。

输入描述

第一行一个正整数 $T$，表示测试数据组数。

对于每组测试数据： 第一行两个正整数 $n, m$，表示时隙数和任务数； 第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示每个时隙的干扰强度； 第三行 $m$ 个正整数 $b_1, b_2, \ldots, b_m$，表示每项任务占用的时隙数。

输出描述

对于每组测试数据，输出一行一个整数，表示峰值干扰的最小值。

数据范围：$1 \le T \le 2 \times 10^5$，所有测试数据的 $n$ 之和 $\le 2 \times 10^5$，$1 \le m \le n$，$1 \le a_i \le 10^9$，$1 \le b_i \le n$，$\sum b_i \le n$。

样例 1

输入：

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

输出：

4
3

说明： - 第一组：第一项任务放在 $[2,3]$（覆盖 $1, 3$，最大值 $3$），第二项放在 $[5,7]$（覆盖 $2, 1, 4$，最大值 $4$），峰值 $\max(3,4)=4$。若要求峰值不超过 $3$，则时隙 $1$、$4$、$7$ 不可用，剩余连续段长度不足以放下长度为 $3$ 的第二项任务。 - 第二组：三项任务分别放在时隙 $1$、$3$ 与 $[4,5]$（覆盖 $2$；$1$；$1,3$），峰值 $\max(2,1,3)=3$。若要求峰值不超过 $2$，则时隙 $2$、$5$ 不可用，无法为第三项任务找到长度为 $2$ 的连续段。

思路

二分答案 + 贪心验证。「峰值干扰的最小值」满足单调性：上限 $x$ 越大越容易安排。

验证 fun(x)：干扰 $\le x$ 的时隙视为可用，任务必须整段放进同一个连续可用段且保持顺序。顺序扫描：累计当前连续可用长度 last，凑够 $b_i$ 就放置并清零；扫描结束前放完全部 $m$ 项则可行。注意不可用时隙会把连续段打断（last 清零）。

在 $[\min a,\ \max a]$ 上二分最小可行 $x$，验证 $O(n)$，总复杂度 $O(n \log \max a)$。

代码

t = int(input())

def solve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    def fun(x):
        bi = 0          # 当前要放的任务
        last = 0        # 当前连续可用段长度
        for i in range(n):
            if a[i] <= x:
                last += 1
                if last == b[bi]:
                    last = 0
                    bi += 1
                    if bi == m:
                        return True
            else:
                last = 0
        return False

    lo, hi = min(a), max(a) + 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if fun(mid):
            hi = mid
        else:
            lo = mid + 1
    print(lo)

for _ in range(t):
    solve()