第3题-待发热度重排

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

短视频后台里躺着 $m$ 条待发稿，第 $i$ 条带着质量分 $p_i$ 和热度分 $h_i$。策划给了一份目标热度排列 $t_1, t_2, \ldots, t_m$，要求排完之后每个位置上的热度刚好等于 $t$。

运营只能按下面的规则对调两条稿件：当且仅当 $p_i \le p_j$ 且 $h_i \le h_j$ 时，才允许把第 $i$ 条和第 $j$ 条互换位置。对调可以做任意多次。

问能否让最终的热度序列与 $t$ 完全一致。能则输出 YES，不能则输出 NO（大小写必须一致）。

输入描述

第一行一个整数 $q$，表示询问组数。（$1 \le q \le 10^2$）

接下来 $q$ 组，每组三行：

• 第一行一个整数 $m$，表示待发条数。（$1 \le m \le 10^5$）
• 第二行 $2m$ 个整数，按 $p_1, h_1, p_2, h_2, \ldots, p_m, h_m$ 给出每条稿的质量分与热度分。（$1 \le p_i, h_i \le 10^5$）
• 第三行 $m$ 个整数 $t_i$，即目标热度排列。（$1 \le t_i \le 10^5$）

保证全部询问的 $m$ 之和不超过 $10^6$。

输出描述

对每组询问输出一行 YES 或 NO。

样例 1

输入：

3
2
1 1 2 3
3 1
2
1 5 2 1
1 5
3
1 4 2 1 3 5
1 4 5

输出：

YES
NO
YES

说明： - 第一组：$(1,1)$ 与 $(2,3)$ 可以互换，热度能变成 $3\ 1$。 - 第二组：$(1,5)$ 与 $(2,1)$ 互不可比，对调不了，热度变不成 $1\ 5$。 - 第三组：三条都能经由可比对调连成一块，热度多重集与目标相同，故可以重排。

样例 2

输入：

2
1
7 7
7
3
1 5 2 3 3 1
1 3 5

输出：

YES
NO

说明： - 第一组：只有一条，热度已是 $7$。 - 第二组：质量升、热度降，两两不可比，只能保持 $5\ 3\ 1$，对不齐 $1\ 3\ 5$。

思路

按 $(p, h)$ 双关键字排序后，位置 $i$ 在 $j$ 前面则必有 $p_i \le p_j$，于是「可交换」当且仅当 $h_i \le h_j$。

考察相邻两段 $[0, r]$ 与 $[r+1, m)$：

• 若前缀的最小热度 $\le$ 后缀的最大热度（pre_min[r] <= suf_max[r+1]），则存在跨段的可比对，两段连通；
• 若前缀最小严格大于后缀最大，则任何跨段对的 $h$ 都是「左大右小」，不可交换——这是一个不可跨越的分割点。

据此把序列切成若干块：块内热度可以任意重排，块与块之间完全隔离。答案为 YES 当且仅当每一块内热度的多重集与目标 $t$ 对应段一致（排序后逐块比较）。前缀最小 / 后缀最大用 itertools.accumulate 一遍预处理，总复杂度 $O(m \log m)$。

代码

from itertools import accumulate

def solve():
    m = int(input())
    vals = list(map(int, input().split()))
    p = vals[0::2]
    h = vals[1::2]
    t = list(map(int, input().split()))

    # 按 (p, h) 排序
    order = sorted(range(m), key=lambda i: (p[i], h[i]))
    hs = [h[i] for i in order]
    ts = [t[i] for i in order]

    # 前缀最小、后缀最大
    pre_min = list(accumulate(hs, min))
    suf_max = list(accumulate(reversed(hs), max))[::-1]

    l = 0
    while l < m:
        r = l
        while r + 1 < m and pre_min[r] <= suf_max[r + 1]:
            r += 1

        if sorted(hs[l:r + 1]) != sorted(ts[l:r + 1]):
            return "NO"
        l = r + 1

    return "YES"


q = int(input())
for _ in range(q):
    print(solve())