聿麟 2012-03-03 20:04:00
点我顶贴
收藏
删除
1.先快排排序，生成链表
2.合并链表最前面2个，计算总代价，将2堆果子的代价相加，生成1个新的节点，然后维护链表（就是遍历一遍，找到比这个代价大的，插入到这个节点的前面），维护链表的时间复杂度是O（n)
3.重复2，直到只剩下最后一个节点....
快排的时间复杂度是O(n log n）
合并果子加上维护是O（n^2)，但是每次合并，节点的数目都会减少，所以实际上远远小于O(n^2)的复杂度
应该AC是无压力的..