[TIOJ] 1429. [APIO '12] 忍者調度問題
題目連結: http://tioj.infor.org/problems/1429 本題其實有很多種寫法，例如：樹剖、整體二分搜、堆(啟發式合併或可合併)，我這裡的做法是用可合併堆的做法，也是裡面最快的一種(?，可以發現對於某個節點，如果已知他所有小孩的選法，那就把那些節點全部混在一起，然後如果超過預算就把最大的移掉，而因為要找最大的，我們需要用到heap，不過我們還需要快速合併多個堆，所以可以採用可合併堆，或是直接啟發式合併就好。 我在這裡採用的可合併堆是配對堆，雖然大家都寫左偏樹，不過我覺得配對堆比較好寫XDD，一種似乎均攤複雜度接近費波那契堆的東東，詳細證明可以看他的 論文 ，不過我也不是很熟，簡單說一下他的做法:合併跟插入都是直接跟根比大小後決定誰當根，所以有可能一個根下面有一堆小孩，為了解決會因此爛掉的狀況，於使我們在pop的時候讓他的小孩們緊縮一點(?，就是pop時就把他的小孩兩兩合併，直到剩一個為止。似乎跟splay tree有點類似，大概這樣吧 註:這裡採用的合併方式因為有點懶人，根據論文他只能證出$O(\frac{log n log log n}{ log log log n})$的上界，不過$ \frac{ \frac{log n log log n}{ log log log n} }{log n}$在$n #include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef long long lld;
#define N 100000
struct pairingNode{
int val;
vector<pairingNode*> child;
};
class pairingHeap{
private:
pairingNode* root;
int count;
public:
lld sum=0;
pairingHeap(){root=NULL;count=0;}
...