1 条题解

  • 0
    @ 2019-09-03 15:13:23

    想到暴力模拟应该很简单,但是时间复杂度不优秀。我们选择数据结构维护。

    我们发现要求某些符合条件的最优值:即每一个程序员[在它吃完美食结束前到达]的[资历最深]的程序员,即符合的条件是吃完美食前到达,最优值是资历最深。最优值?这不就是优先队列嘛。因此我们可以用优先队列来维护。

    具体做法是:

    暴力找出第一个吃美食的程序员:按照到达时间为第一关键字,按照资历为第二关键字的顺序的第一个元素。然后将其放入堆中。

    如果堆是空的:新放进去。

    如果不为空:顺序查找来到时间小于这个程序员吃美食结束的程序员,进堆;以经验为第一关键字。每一次的堆顶就是即将吃的美食。

    预处理:预处理经验值,第i个可以认为是 n−i+1

    时间复杂度:不高于O(nlogn)

  • 1

信息

ID
1286
难度
3
分类
数据结构 | 队列模拟 点击显示
标签
递交数
0
已通过
0
通过率
?
被复制
2
上传者