思路:贪心
首先观察一下数据范围,n≤105,1≤ai≤109,我们知道232>109,因此对一个数字至多操作32次,就可以将其变为1,因此,我们总共的操作次数最坏情况也不会超过32n,因此我们可以直接模拟整个过程。
贪心地考虑:我们最终只需要保证这n个数字的最大值和最小值相等,即可保证所有的数字都相等,那么我们一定是优先操作最大数,我们可以使用大根堆去维护所有的竹子,每次将大根堆的堆顶元素(最大值)弹出,然后将其/2,然后在定义一个变量minv动态维护竹子的最小值,当大根堆的堆顶元素的值与minv相等时,则说明已经满足题目要求,直接输出操作次数即可。
代码