之前我一直看不太懂原 PO 想做什么
刚刚再重新看了新推文之后才应该是弄懂了...
原 PO 想要的应该是这样
现在他手上有很多球 有红球跟绿球
他想要用一个程序将取球机率分配给这些球
使得可能的话取出来的球是红球的机率是 75% 绿球是 25% 这样
这样的话有些关键问题应该可以问一下:
在取球过程中球会不会增减？球会不会变色？
如果两个问题都是否的话那其实不管资料量大不大
直接用一开始的红绿分堆法 (也就是 goliathplus 回的程式片段) 就够了
反正球就是那些 分只要分一次就好 之后就是拼命取球就行了
(都分堆了那有没有红球或绿球也很容易就能判断)
原 PO 会想要问可能就是这两个问题中至少有一个为是
不过就我来看 即使是这样 加上一些适当的定位法的话也是可以分堆解决的
(例如说两堆各用一个 std::set 存球之类的)
因为球的增减就是把某个球放进或拿出某堆
球的变色就是把某球从一堆抓到另一堆
只要我们可以够快地找到球 (std::set 的 O(log n) 应该够用了...)
这两件事就都可以简单达成
==
也就是说我的着眼点反而不在于取球了
因为如果能分堆那取球就很简单 所以问题就变成了将球分堆难不难
在我看来这几种状况下要让球分堆(且保持分堆)应该不怎么难才是
==
不过上面还是有种状况没考虑到
如果过一段时间球会整篮换掉的话那就有点麻烦了
偶尔整篮换一次还能够接受 常常整篮换的话可能就要考虑分堆之外的做法了...