1 条题解

  • 0
    @ 2024-8-9 16:02:54

    维护一个小根堆,那么每一次判断堆顶能不能改,能的话就改成目前的 cic_i。统计修改次数,最多改 bib_i 个。这样的复杂度是 O(nmlogn)\mathcal O(nm\log n) 的不能接受。

    这个做法慢是慢在一个数被多次修改了,我们以 cic_i 为关键字从大到小排序,那么每一个数最多只会被修改一次,这样的复杂度是 O((n+m)logn)\mathcal O((n+m)\log n) 的。

    • 1

    信息

    ID
    1108
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    44
    已通过
    13
    上传者