Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:一次快排后,已经有序了,继续用快排退化成冒泡,所以tle?后来用插入就能过

Posted by lizimeng at 2016-08-17 15:23:42 on Problem 3253
In Reply To:一次快排后,已经有序了,继续用快排退化成冒泡,所以tle?后来用插入就能过 Posted by:nkzengjing at 2014-09-20 23:29:47
不用每次都排序啊,同学!!!你每次找出来最短的两个拼就好了。找最小的两个值就可以,这个时间复杂度只有O(n)。每次排序太不经济。
如果你嫌这个时间复杂度高,还可以用堆实现数据管理,那样的话,取最小值只需要O(log n)的时间复杂度。你不需要自己亲自实现,用STL提供的优先队列就可以。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator