讲个笑话
MWL_wma
·
·
题解
发现操作 1 是好 \Theta(1) 做的，瓶颈在于考虑操作 2。
感觉这个操作 2 稀里糊涂的很难搞啊，于是我们开始寻找性质。
注意到一次操作最多让一个数字增加 1，于是热爱跟好的我们发现这题可以根号分治！
具体来讲就是这样：我们发现数组中不小于 \sqrt{q} 的数出现次数一定不超过 \sqrt{q} 个，因为每产生一个满足条件的数都至少需要进行 \sqrt{q} 次操作，q 次操作最多产生 \frac{q}{\sqrt{q}}=\sqrt{q} 个满足要求的数。
所以我们对每个不小于 \sqrt{q} 的数暴力地做操作 2，对小于 \sqrt{q} 的数我们依次对等于 1,2,\dots,\sqrt{q} 的数统一做操作 2。
时间复杂度 \Theta(q^\frac{3}{2})，喜提最劣解。