Readme

3495.Minimum-Operations-to-Make-Array-Elements-Zero

对于[a,b]区间，理论上我们可以计算出将每个元素变为0需要有多少次“/4”的操作，也就是将其转化为一个递增数列p=[x1,x2,x3,...,xn]，每个元素代表该数需要x次“/4”才能变成0。我们将该数列的总和记作M。根据题意，我们每个回合可以在p里找两个不同的元素减1，问至少需要多少回合将所有元素置零？直观上，我们只要贪心地做到每回合找到两处非零数，那么总回合大致就是M的一半。那么我们是否一定能在每个回合针对两个不同的数进行操作呢？事实上，只要不存在最大的x超过总数的一半，我们总能实现这样的配对。这里简单证明一下。

首先必要性。如果xn>M/2，那么即使其他所有元素每次都找xn配对，削减之后xn仍有剩余，接下来就无法在一个回合里做两次削减。根据逆否原理，要实现每个回合能削减两个数，必然要xn<=M/2.

其次充分性。如果xn<=M/2，我们可以找到一个分解点xi恰好将M分成相等两半，将[x1..xi]与[xi...xn]放入两个抽屉，每次必然能各从每个抽屉里取出不一样的两个元素。特别地，对于xi而言，因为xi必然也小于M/2（回合总数），所以我们必然可以构造出每个回合的配对不同时出现xi。

由此，本题的基本思路是：计算[x1,x2,x3,...,xn]的总和M，以及最大元素需要的操作次数B。如果B小于等于M的一半，那么答案就是(M+1)/2，其中+1是为了处理M为奇数的情况。反之，我们令A=M-B表示能凑成配对的回合，答案就是A+(B-A).

接下来我们思考如何求M。首先[a,b]里所有的元素都能至少除4一次。其次[4,b]里的所有的元素都至少能再做一次除4，所以我们需要判断[4,b]与[a,b]的交集部分。接下来[16,b]里的所有的元素都至少能再做一次除4，同里我们需要判断[16,b]与[a,b]的交集部分... 依次类推，我们维护一个起始点x=1，每次x都不断自乘4，M就可以增加max(x,a)到b这部分区间的元素个数。这样我们就统计了[a,b]里面所有的元素总共可以做几次除4的操作。