笔试时间：2025年9月13日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：平衡树

小明有一个数组a，长度为n（保证n是奇数）。其中的中位数定义为：如果将这个数组排序，则最中间的那个元素即为中位数。小明每次可以选择数组中的一个数，将它加1或减1。他想知道，最少经过多少次这样的操作，可以让这个数组的中位数变成m。

输入描述

第一行一个整数T，表示数据组数。对每组数据：

• 第一行两个整数n，m，表示数组大小和期望的中位数
• 第二行n个整数a[i]，表示数组初始状态

输出描述

对于每组数据，输出一行一个整数，表示答案。

样例输入

2

5 3

1 2 2 4 5

7 10

8 5 8 11 8 67 15

样例输出

1

2

对于第一组样例，把任意一个2增加1即可。

参考题解

解题思路：

1. 首先对数组进行排序
2. 中位数的位置固定为n/2
3. 根据当前中位数与目标值m的关系：
1. 如果当前中位数小于m，需要将中位数及其右边小于m的元素都调整到m
2. 如果当前中位数大于m，需要将中位数及其左边大于m的元素都调整到m
3. 如果相等，则不需要操作

C++：

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        sort(a.begin(), a.end());
        int midIndex = n / 2;
        long long operations = 0;
        
        if (a[midIndex] < m) {
            for (int i = midIndex; i < n; i++) {
                if (a[i] < m) {
                    operations += (m - a[i]);
                } else {
                    break;
                }
            }
        } else if (a[midIndex] > m) {
            for (int i = midIndex; i >= 0; i--) {
                if (a[i] > m) {
                    operations += (a[i] - m);
                } else {
                    break;
                }
            }
        }
        
        cout << operations << "\n";
    }
    
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] a = new int[n];
            
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            
            Arrays.sort(a);
            int midIndex = n / 2;
            long operations = 0;
            
            if (a[midIndex] < m) {
                for (int i = midIndex; i < n; i++) {
                    if (a[i] < m) {
                        operations += (m - a[i]);
                    } else {
                        break;
                    }
                }
            } else if (a[midIndex] > m) {
                for (int i = midIndex; i >= 0; i--) {
                    if (a[i] > m) {
                        operations += (a[i] - m);
                    } else {
                        break;
                    }
                }
            }
            
            System.out.println(operations);
        }
        
        sc.close(