2019正睿Day2题解
T1石子stone
T2内存memory
T3子集subset内存
对于每个r,考虑如果用它水压缩那么可以达到的最优解,设为F()
假如给定一个m、想要求F(x),那么可以通过二分贪心在(log2m)的时间内
算出。
直接对于所有x都暴力计算即可得到Q(mlog2m)的复杂度,可以通过子任务
1.2
如果我们以随机顺序遍历所有x,则在期望情况下,新的F(x)比当前所有F的
值都要小的r个数的期望应该是∑1/,这是调和级数,为e(lnm)。
于是我们只对于这些x二分即可: