思路：思维

记大于 $a_0$ 的数有 $x$ 个

• 如果 $x>1$ ，则让 $a_0$ 乘 $2$ 。
  令 $b$ 为大于 $a_0$ 的数构成的数组，$cnt_i$ 为 $b_i$ 降到小于等于 $a_0$ 的次数。

  假设每个数都 $b_i$ 都满足 $a_0+1\leq b_i\leq 2 a_0$

  那么要使得每个数都小于等于 $a_0$ ，选择乘法只需要 $1$ 次，选择除法需要 $x$ 次，$x>1$ 。

• 如果 $x=1$ ，则让那个数除 $2$ 下取整。 因为考虑 $a_0=3$ ,大于 $a_0$ 的数为 $7$ 。

  此时让 $a_0$ 乘 $2$ 为 $6$ 仍然小于 $7$. 而让 $7$ 除 $2$ 下取整为 $3$ ，此时 $a_0=\lfloor\frac{7}{2}\rfloor$ 。

时间复杂度：$O(n\log n)$

代码

c++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 1; i < n; ++i)
        if (a[i] > a[0]) q.push(a[i]);

    int ans = 0;
    while (!q.empty()) {
        if (q.size() > 1) {
            ans += 1;
            a[0] *= 2;
            while (!q.empty() && q.top() <= a[0]) q.pop();
        } else {
            int t = q.top();
            q.pop();
            while (t > a[0]) {
                ans += 1;
                t /= 2;
            }
        }
    }

    cout << ans << "\n";
     
    return 0;
}

python

n = int(input())
nums = list(map(int, input().split()))
from collections import *
def solve(n, nums):
    res = 0
    candi = nums[0]
    nums = nums[1:]
    nums.sort()
    stack = deque()
    for i in range(0, n-1):
        if nums[i] > candi:
            stack.append(nums[i])
    if len(stack) == 0:
        return 0
    while stack:
        if len(stack) > 1:
            candi *= 2
            res += 1
            while stack and stack[0] <= candi:
                stack.popleft()
        else:
            t = stack.popleft()
            while t > candi:
                res += 1
                t //= 2

    return res
print(solve(n, nums))

java

import java.util.*;


class Main{

    static int res;
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        int count = scanner.nextInt();
        scanner.nextLine();

        int[] cnt = new int[count];

        for(int i = 0; i < count; i++){
            cnt[i] = scanner.nextInt();
        }

        int a0 = cnt[0];
        int x = compareBig(cnt, a0);
        while(x > 1){
            cnt[0] *= 2;
            x = compareBig(cnt, cnt[0]);
            res++;
        }

        if(x == 0){
            System.out.println(res);
            return;
        }
        a0 = cnt[0];
        Arrays.sort(cnt);
        int b0 = cnt[cnt.length - 1];
        while(b0 >= 2 * a0){
            b0 /= 2;
            res++;
        }
        if(a0 + 1 <= b0){
            res++;
        }
        System.out.println(res);

    }


    public static int compareBig(int[] nums, int a0){
        int res = 0;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > a0){
                res++;
            }
        }

        return res;
    }


}

题目描述

小美有一个长度为 $n$ 的数组 $a$ 。他需要将这个数组中第一个元素 $a_0$ 变成这个数组中的最大数。

小美有如下两种操作，

• 将 $a_0$ 乘 $2$
• 选择一个 $i(1\leq i <n)$，使得 $a_i$ 变成 $\lfloor\frac{a_i}{2}\rfloor$

现在小美问你，他至少要多少次操作才能使得 $a_0$ 变成最大数。

输入描述

第一行，一个正整数 $n(1\leq n\leq 10^5)$ ，代表数组的大小。

第二行输入 $n$ 个正整数表示数组 $a$ ，第 $i$ 个数为 $a_i(1\leq a_i\leq 10^9)$ 。

输出描述

一个整数，表示使得 $a_0$ 变成最大数的最小操作次数

样例

输入

6
1 1 4 4 1 4

输出

2

说明

将 $1$ 乘两次 $2$ 。