随笔-8  评论-5  文章-0  trackbacks-0

唉,没有《金牌之路》就是不爽,这道题目又说是那本书上有的,好像要用到max heap和min heap。
Any way, I can use my own way now.
把box的内容按照输入的顺序存放到array中。我们看到u(N)就是GET操作,相当于在array的前u(N) 个元素中找i-minimum元素。如果array的前u(N)个元素按递增排序好了,那么只要取array[i]就行了。
现在的关键是提高排序的速度。假设u(k)的时候,array[0] .... array[u(k)-1]已经排好序,那么只要先对array[u(k)] ... array[u(k+1)-1]排序,再把二者合并起来就行了。C++ STL提供了所有的功能,sort和merge函数可以直接拿来用。

posted on 2005-08-03 20:51 pumpkin 阅读(260) 评论(0)  编辑 收藏 引用
只有注册用户登录后才能发表评论。