点这里查看
讨论 / 我问下25题(果实合并)的思想,如何贪心?
3230391 2008-05-16 07:32:00
点我顶贴 收藏 删除
我的思想是始终把最小的两堆合并,一直到只有一堆

但数据只过的了几个点(居然还有超时?~~)~~~~~

有没有人可以给我讲下?

#1 我是天才他哥@2008-05-16 05:31:00
回复 删除
很明显LZ，你的思想有问题，我可以举出范例，因为我以前也这么想。

但是确切的说，我也不会

#2 wish@2008-05-16 07:32:00
回复 删除
就是这么贪的～

先快排一下

然后删除最小的两个，这两堆石子并成一堆，把这一堆再插入到原来的数组中

n 堆总共进行 n - 1 次，这样就只剩一堆了

算法主要的瓶颈是插入的操作

不过这题直接模拟插入＋移动元素（类似朴素插入排序）就可以AC了

最坏复杂度 O(n^2)，但是一般不会出现这种情况

如果想要优化的话可以使用 SBT 加速

复杂度 O(nlgn)

如果需要程序的话可以联系我：QQ 918874465

查看更多回复
提交回复