ABC323D Merge Slimes
题目简述
小 A 有 \(N\) 种橡皮泥。对于第 \(i\) 种橡皮泥，它的大小为 \(S_i\) 且一共有 \(C_i\) 个。
小 A 可以合成两个大小相同的橡皮泥，若这两个橡皮泥大小为 \(X\)，则新和成的橡皮泥大小为 \(2X\)。
小 A 想知道，在进行若干次合成后（有可能 \(0\) 次），他能获得的最小的橡皮泥的种类数是多少。
思路
要尽量多地进行合成操作，很容易想到从小到大地合成橡皮泥。
每次要合成当前大小最小的橡皮泥，合成之后要么剩余 \(0\) 个，要么剩余 \(1\) 个。如果剩余 \(1\) 个，则之后无论怎样合成都不能消除掉，故对答案产生 \(1\) 的贡献。
可以用优先队列维护数量大于 \(1\) 的橡皮泥，每次取出队列中大小最小的橡皮泥进行更新。