Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

Re:Re：貌似官方题解好像会退化，不懂是怎么处理的。。。

Posted by hkrcn at 2010-03-10 22:03:16 on Problem 3017
In Reply To:Re:Re：貌似官方题解好像会退化，不懂是怎么处理的。。。 Posted by:DreamOfGame at 2009-09-08 10:08:57

私以为官方题解没有问题。
对于每个数字，最多加入一次双向队列/优先队列，最多从双向队列/优先队列删除一次。
优先队列是利用堆实现，所有操作都可以在O(log2 n)内解决，最多操作O(n)次，时间复杂度为O(n log2 n)；
对于双开队列，加入一个数的时候，需要在进行一次二分查找，O(log2 n)，其余都是O(1)的，最多操作O(n)次，时间复杂度为O(n log2 n)。
综上，时间复杂度为O(n log2 n)

Followed by:

Post your reply here:

Home Page Go Back To top