笔试时间：2024年03月19日

历史笔试传送门：2023秋招笔试合集

第一题

题目：开幕式排练

导演在组织进行大运会开幕式的排练，其中一个环节是需要参演人员围成一个环形。演出人员站成了一圈，出于美观度的考虑，导演不希望某一个演员身边的其他人比他低太多或者高太多。现在给出n个参演人员的身高，问在他们站成一圈时，相邻演员的身高差的最大值至少是多少? 请你帮忙计算。

输入描述

输入包括两行，第一行有1个正整数，代表人数 n。

第二行有n个空格隔开的正整数h表示第i个演员的身高。

输出描述

输出包括一个正整数，表示答案。

样例输入一

5

2 1 1 3 2

样例输出一

1

样例输入二

2

10 20

样例输出二

10

说明：样例1中排为1, 2, 3, 2, 1即可；样例2中排为10, 20即可。

参考题解

采用 贪心 的思想：先将数组元素从小到大排序，然后再声明一个新的数组，轮流尾插/头插元素，这样可以使得相邻两个人的身高差最小。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n; 
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) 
        cin >> arr[i];
    
    sort(arr.begin(), arr.end());
    
    vector<int> ans;
    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0) 
            ans.push_back(arr[i]);
        else 
            ans.insert(ans.begin(), arr[i]);
    }
    
    int res = abs(ans.front() - ans.back());
    for (int i = 1; i < n; ++i) {
        res = max(res, abs(ans[i] - ans[i - 1]));
    }
    cout << res;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> arr = new ArrayList<>();
        for (int i = 0; i < n; ++i)
            arr.add(scanner.nextInt());

        Collections.sort(arr);

        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0)
                ans.add(arr.get(i));
            else
                ans.add(0, arr.get(i));
        }

        int res = Math.abs(ans.get(0) - ans.get(ans.size() - 1));
        for (int i = 1; i < n; ++i) {
            res = Math.max(res, Math.abs(ans.get(i) - an