1 条题解
-
0
何老师 (root) LV 0 MOD @ 2019-09-03 15:13:23
想到暴力模拟应该很简单,但是时间复杂度不优秀。我们选择数据结构维护。
我们发现要求某些符合条件的最优值:即每一个程序员[在它吃完美食结束前到达]的[资历最深]的程序员,即符合的条件是吃完美食前到达,最优值是资历最深。最优值?这不就是优先队列嘛。因此我们可以用优先队列来维护。
具体做法是:
暴力找出第一个吃美食的程序员:按照到达时间为第一关键字,按照资历为第二关键字的顺序的第一个元素。然后将其放入堆中。
如果堆是空的:新放进去。
如果不为空:顺序查找来到时间小于这个程序员吃美食结束的程序员,进堆;以经验为第一关键字。每一次的堆顶就是即将吃的美食。
预处理:预处理经验值,第i个可以认为是 n−i+1
时间复杂度:不高于O(nlogn)
- 1