题目解析
枚举;贪心
从小到大枚举使用的手指数量;
对于枚举的手指数量为 XXX,存储每个手指下一次可以点击音符的最早时间 a1,a2,⋯ ,aXa_1, a_2, \cdots, a_Xa1 ,a2 ,⋯,aX ,遍历所有的音符,对于每个到来的音符 iii 使用选择手指 jjj 满足 aj=min(a1,a2,⋅,aX)a_j = \min{(a_1, a_2, \cdot, a_X)}aj =min(a1 ,a2 ,⋅,aX ),来尝试点击这个音符,并且尽可能早地点击这个音符,即 max(aj,ti−30)\max{(a_j, t_i - 30)}max(aj ,ti −30)。这样我们便可以保证在使用 XXX
个手指的情况下,使得每个音符都可以在允许的最早的时刻被点击。
时间复杂度 O(N)\mathrm{O}(N)O(N)。
AC代码