笔试时间：2025年9月13日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

小明有一个长度为n的数组a。小明可以对数组执行至多k次如下操作：指定数组中的某个元素aᵢ，令aᵢ = aᵢ + 1。对于同一个位置的元素可以多次进行操作。小明想要最小化数组中相邻元素的差的绝对值的最大值，请你帮助他计算。

输入描述

输出描述

对于每组测试数据，输出一个正整数，表示经过操作后数组中相邻元素的差的绝对值的最大值最小是多少

样例输入

1

5 3

3 1 5 4 1

样例输出

2

参考题解

解题思路：

1. 使用二分答案的方法，二分查找最小可能的最大差值x
2. 对于每个候选的x，用check函数判断是否能在最多k次操作内使所有相邻差不超过x
3. check函数通过两次传递（正向和反向）来构造满足条件的数组： 正向传递：确保每个元素至少为前一个元素减去x反向传递：确保每个元素至少为后一个元素减去x
4. 计算总操作次数，判断是否不超过k

C++：

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

bool check(int x, int n, int k, vector<int>& a) {
    vector<int> b1(n), b2(n);
    b1[0] = a[0];
    for (int i = 1; i < n; i++) {
        b1[i] = max(a[i], b1[i-1] - x);
    }
    
    b2[n-1] = b1[n-1];
    for (int i = n-2; i >= 0; i--) {
        b2[i] = max(b1[i], b2[i+1] - x);
    }
    
    int total_cost = 0;
    for (int i = 0; i < n; i++) {
        total_cost += b2[i] - a[i];
    }
    return total_cost <= k;
}

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    int max_val = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        max_val = max(max_val, a[i]);
    }
    
    int low = 0, high = max_val, ans = max_val;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (check(mid, n, k, a)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << ans << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Java：

import java.util.*;

public class Main {
    static boolean check(int x, int n, int k, int[] a) {
        int[] b1 = new int[n];
        int[] b2 = new int[n];
        b1[0] = a[0];
        
        for (int i = 1; i < n; i++) {
            b1[i] = Math.max(a[i], b1[i-1] - x);
        }
        
        b2[n-1] = b1[n-1];
        for (int i = n-2; i >= 0; i--) {
            b2[i] = Math.max(b1[i], b2[i+1] - x);
        }
        
        int totalCost = 0;
        for (int i = 0; i < n; i++) {
            totalCost += b2[i] - a[i];
        }
        return totalCost <= k;
    }
    
    static void solve(Scanner sc) {
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        int maxVal = 0;
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            maxVal = Math.max(maxVal, a[i]);
        }
        
        int low = 0, high = maxVal, ans = maxVal;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (check(mid, n, k, a)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        System.out.println(ans);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            solve(sc);
        }
    }
}

Python：

def check(x, n, k, a):
    b1 = [0] * n
    b1[0] = a[0]
    for i in range(n - 1):
        b1[i + 1] = max(a[i + 1], b1[i] - x)
    
    b2 = [0] * n
    b2[n - 1] = b1[n - 1]
    for i in range(n - 2, -1, -1):
        b2[i] = max(b1[i], b2[i + 1] - x)
    
    total_cost = 0
    for i in range(n):
        total_cost += b2[i] - a[i]
    return total_cost <= k

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    max_val = max(a)
    
    low, high, ans = 0, max_val, max_val
    while low <= high:
        mid = (low + high) // 2
        if check(mid, n, k, a):
            ans = mid
            high = m