1 条题解

  • 0
    @ 2026-11-15 15:17:19

    题目分析

    50 分做法

    首先把所有音符排序。对于每个音符,暴力预处理出以它作为一首乐曲中最低音时,最多能往后添加多少个音符。然后枚举两个音符分别作为两首乐曲的最低音,统计答案。时间复杂度 O(n2)O(n^2)。

    100 分做法

    用单调队列滑动窗口,可以在 O(n)O(n) 的时间内求出排序后每个音符能添加的音符数量。

    接下来只需要从后往前记录「截止到每个位置,前面所有音符能添加的音符数量」的前缀最大值,然后再从前往后枚举第一个乐曲的最低音,配合前缀最大值即可 O(n)O(n) 求出答案。总时间复杂度 O(nlog⁡n)O(n \log n)(瓶颈在排序)。

    • 1

    信息

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