笔试时间：2025年8月26日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：你的一半归我了

给定正整数 n 和一个大小为 n 的数组 a。小钟可以对这个数组执行若干次以下操作：选择一个下标 i 令 X = [aᵢ/2]（即向下取整），令 a₁ = a₁ + x，aᵢ = aᵢ - x。小钟需要求出最少的操作次数使得 a₁成为数组中最大的元素，即对于任意的 i（2≤i≤n）满足 aᵢ < a₁。题目保证给定数据一定存在解。请你计算出最少的操作次数是多少。

输入描述

输入包括多组测试数据。

输入第一行包括一个正整数 T（1≤T≤100），表示测试数据的组数。

每组测试数据的第一行有一个整数 n（1 ≤ n ≤ 10⁵），表示数组大小；

接下来的一行有 n 个整数 a₁,a₂,…,aₙ（2 ≤ aᵢ ≤ 10⁹），表示题目给定的数组。

保证每个测试点的所有测试数据的 n 的和不超过 2×10⁵。

输出描述

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

样例输入

2

3

2 4 5

2

3 3

样例输出

2

0

提示：对于第一组测试数据，可以选择下标 3，数组变为 [4,4,3]，然后选择下标 2，数组变为 [6,2,3]，此时 a1 是数组中最大的元素，操作次数为 2。可以证明不存在更少的操作次数使得 a1 成为最大的元素。 对于第二组测试数据，由于 a1 本来就已经是最大元素，故不需要进行任何操作。

参考题解

核心思路是：为了让 a_1 尽快成为数组中的最大值，每次操作都应该选择当前 a_2 至 a_n 中最大的那个元素。这是因为对越大的数 a_i 进行操作，a_1 获得的增量 x (即 a_i 的一半) 就越大，从而能以最快的速度追赶并超越其他元素。为了高效地找到并更新这个当前最大值，代码使用了一个大顶堆（PriorityQueue）来存储 a_2 到 a_n 的所有元素。循环不断地从堆顶取出最大值进行操作，直到 a_1 大于堆中所有元素为止，操作次数即为最少次数。

C++：

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t-- > 0) {
        int n;
        long long a1;
        cin >> n >> a1;
        
        // 最大优先队列（默认是最大堆）
        priority_queue<int> pq;
        for (int i = 1; i < n; ++i) {
            int num;
            cin >> num;
            pq.push(num);
        }
        
        long long operations = 0;
        // 当队列不为空且a1小于等于当前最大元素时，继续操作
        while (!pq.empty() && a1 <= pq.top()) {
            int currentMax = pq.top();
            pq.pop();
            
            int x = currentMax / 2;
            a1 += x;
            pq.push(currentMax - x);  // 将剩余部分放回队列
            operations++;
        }
        
        cout << operations << endl;
    }
    return 0;
}

Java：

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       int t = scanner.nextInt();
       while (t-- > 0) {
           int n = scanner.nextInt();
           long a1 = scanner.nextLong();

           PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
           for (int i = 1; i < n; i++) {
               pq.add(scanner.nextInt());
           }

           long operations = 0;
           while (!pq.isEmpty() && a1 <= pq.peek()) {
               int currentMax = pq.poll();
               int x = currentMax / 2;
               a1 += x;
               pq.add(currentMax - x);
               operations++;
           }
           System.out.println(operations);
       }
       scanner.close();
   }
}

Python：

import heapq

t = int(input())
for _ in range(t):
    n, a1 = map(int, input().split())
    
    # Python的heapq是最小堆，用负值实现最大堆
    max_heap = []
    for _ in range(n-1):
        num = int(input())
        heapq.heappush(max_heap, -num)  # 存储负值
    
    operations = 0
    # 当堆不为空且a1小于等于当前最大元素时，继续操作
    while max_heap and