50 分做法
首先把所有音符排序。对于每个音符,暴力预处理出以它作为一首乐曲中最低音时,最多能往后添加多少个音符。然后枚举两个音符分别作为两首乐曲的最低音,统计答案。时间复杂度 O(n2)O(n^2)O(n2)。
100 分做法
用单调队列滑动窗口,可以在 O(n)O(n)O(n) 的时间内求出排序后每个音符能添加的音符数量。
接下来只需要从后往前记录「截止到每个位置,前面所有音符能添加的音符数量」的前缀最大值,然后再从前往后枚举第一个乐曲的最低音,配合前缀最大值即可 O(n)O(n)O(n) 求出答案。总时间复杂度 O(nlogn)O(n \log n)O(nlogn)(瓶颈在排序)。
使用您的 Hydro 通用账户