思路分析

我们希望 尽可能快地让 $a_1$ 成为最大值。直觉上，每次应该从当前最大的 $a_i$ （ $i \ge 2$ ）转移值到 $a_1$ ，这样 $a_1$ 增长最快，其他元素尽快下降。

因此可以：

P3476.第1题-你的一半归我了

1000ms

Difficulty: 2

所属公司 : 滴滴

算法与标签>贪心算法

给定正整数 $n$ 和一个大小为 $n$ 的数组。小种可以对这个数组执行若干次以下操作:选择一个下标 $i$ 令 $x=[\frac{a_i}{2}]$ (即向下取整)，令 $a_1=a_1+x,a_i=a_i-x$ 。

小钟需要求出最少的操作次数使得 $a_i$ 成为数组中最大的元素，即对于任意的 $i(2 <=i<=n)$ 满足 $a_i<a_1$ 。题目保证给定数据一定存在答案。

请你计算出最少的操作次数是多少。

输入包括多组测试数据。

输入第一行包括一个正整数 $T(1<=T<=100)$ ，表示测试数据的组数。

每组测试数据的第一行有一个整数 $n(1 <=n<=10^5)$ ，表示数组的大小;

接下来的一行有 $n$ 个整数 $a_1,a_2,…,a_n(2 <=a_i<=10^9)$ ，表示题目给定的数组。

保证每个测试点的所有测试数据的 $n$ 的和不超过 $2*10^5$ 。

对于每组测试数据，输出一个正整数表示使得 $a_i$ ，成为最大元素的最少的操作次数。

输入

输出

2
0

对于第一组测试数据，可以选择下标 $3$ ，数组变为 $[4,4,3]$ ，然后选择下标 $2$ ，数组变为 $[6,2,3]$ ,此时 $a_1$ 是数组中最大的元素，操作次数为 $2$ 。可以证明不存在更少的操作次数使得 $a_1$ 成为最大的元素。

对于第二组测试数据,由于 $a_1$ 本来就已经是最大元素，故不需要进行任何操作。

输入

预期输出（选填）