之前我一直看不太懂原 PO 想做什麼
剛剛再重新看了新推文之後才應該是弄懂了...
原 PO 想要的應該是這樣
現在他手上有很多球 有紅球跟綠球
他想要用一個程序將取球機率分配給這些球
使得可能的話取出來的球是紅球的機率是 75% 綠球是 25% 這樣
這樣的話有些關鍵問題應該可以問一下:
在取球過程中球會不會增減？球會不會變色？
如果兩個問題都是否的話那其實不管資料量大不大
直接用一開始的紅綠分堆法 (也就是 goliathplus 回的程式片段) 就夠了
反正球就是那些 分只要分一次就好 之後就是拼命取球就行了
(都分堆了那有沒有紅球或綠球也很容易就能判斷)
原 PO 會想要問可能就是這兩個問題中至少有一個為是
不過就我來看 即使是這樣 加上一些適當的定位法的話也是可以分堆解決的
(例如說兩堆各用一個 std::set 存球之類的)
因為球的增減就是把某個球放進或拿出某堆
球的變色就是把某球從一堆抓到另一堆
只要我們可以夠快地找到球 (std::set 的 O(log n) 應該夠用了...)
這兩件事就都可以簡單達成
==
也就是說我的著眼點反而不在於取球了
因為如果能分堆那取球就很簡單 所以問題就變成了將球分堆難不難
在我看來這幾種狀況下要讓球分堆(且保持分堆)應該不怎麼難才是
==
不過上面還是有種狀況沒考慮到
如果過一段時間球會整籃換掉的話那就有點麻煩了
偶爾整籃換一次還能夠接受 常常整籃換的話可能就要考慮分堆之外的做法了...