1 条题解

  • 0
    @ 2026-11-15 14:01:47

    题目分析

    50 pts

    我们很容易得到一个贪心的算法:把最小的 AA 和最大的 BB 配对,第二小的 AA 和第二大的 BB 配对 ...... 最大的 AA 和最小的 BB 配对。

    这事实上是一个插入排序,每次 O(n)O(n) 判断,最终复杂度 O(n2)O(n^2)

    100 pts

    注意到所有 AA 和 BB 不超过100。

    利用这个条件,我们维护列表 totAtotA:totA[i]totA[i] 表示大小为 ii 的 AA 有多少个

    同理定义 totBtotB

    这样在得到新的 A,BA, B 时,我们可以 O(1)O(1) 的将其插入。

    在回答询问时,我们只需维护两个指针 pp 和 qq,设 totA[p]totA[p] 和 totB[q]totB[q] 的较小者为 TT,将两者都减去 TT,得到 TT 对 (totA[p],totB[q])(totA[p],totB[q]),然后继续移动两个指针即可。

    时间复杂度 O(100n)O(100 n)。

    • 1

    信息

    ID
    81
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者