题解思路

关键观察

只能“加”，不能“减”。因此想要让相邻差变小，只能把较小的那个数往上抬。

把答案（相邻差最大值）记为 X，考虑判定问题：

是否能用不超过 k 次加一操作，使得最终数组 b 满足

1. b[i] ≥ a[i]（因为只能加），
2. |b[i]-b[i+1]| ≤ X（1 ≤ i < n）

如果能判定一个 X 是否可行，就可以对 X 二分查找得到最小可行值。

可行性判定（两趟“推高”法）

约束 |b[i]-b[i+1]| ≤ X 等价于：

• b[i] ≥ b[i-1]-X（从左约束右）
• b[i] ≥ b[i+1]-X（从右约束左）

再加上下界 b[i] ≥ a[i]。为了在满足所有约束下“花的增量最少”，对每个位置都取能取到的最小值即可。

最小解可用两趟线性扫描得到：

1. 先把 b 设为 a。
2. 正向一趟：b[i] = max(b[i], b[i-1]-X)（保证右侧不低于左侧 - X）。
3. 反向一趟：b[i] = max(b[i], b[i+1]-X)（保证左侧不低于右侧 - X）。

完成后 b 是满足所有限制的分量最小数组，因此所需总加和 Σ(b[i]-a[i]) 也是最小的。 若该和 ≤ k，则 X 可行；否则不可行。

二分边界

• 下界 L = 0
• 上界 R = max_{i} |a[i]-a[i+1]|（不做操作时的最大相邻差，显然可行）

每次用上述判定在 O(n) 时间完成，整体 O(n log R)。

复杂度分析

• 判定函数：两趟线性扫描，时间 O(n)，空间 O(1)（就地或开一份拷贝）。
• 二分次数：log₂(R-L+1)，其中 R ≤ 1e9，约 30 次。
• 总复杂度：O(n log 1e9)，满足 n ≤ 2×10^5 的数据要求。
• 注意使用 64 位整型统计增量总和（k 和数组值都可能很大）。

代码实现

Python

import sys

def need_ops(a, X):
    """给定X，返回把数组抬到|相邻差|<=X所需的最小加法次数"""
    n = len(a)
    b = a[:]  # 复制一份作为工作数组
    # 正向：右侧至少为 左侧-X
    for i in range(1, n):
        if b[i] < b[i-1] - X:
            b[i] = b[i-1] - X
    # 反向：左侧至少为 右侧-X
    for i in range(n-2, -1, -1):
        if b[i] < b[i+1] - X:
            b[i] = b[i+1] - X
    # 计算总加法次数（可能很大，用Python int即可）
    s = 0
    for i in range(n):
        s += b[i] - a[i]
    return s

def solve():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    T = int(next(it))
    out = []
    for _ in range(T):
        n = int(next(it)); k = int(next(it))
        a = [int(next(it)) for _ in range(n)]
        # 设二分区间
        R = 0
        for i in range(n-1):
            d = abs(a[i] - a[i+1])
            if d > R: R = d
        L = 0
        # 二分最小可行X
        while L < R:
            mid = (L + R) // 2
            if need_ops(a, mid) <= k:
                R = mid
            else:
                L = mid + 1
        out.append(str(L))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()

Java（类名 Main，使用 BufferedReader+StringTokenizer）

import java.io.*;
import java.util.*;

/* 邻项差值最小化：二分答案 + 两趟推高判定 */
public class Main {
    static long needOps(long[] a, long X) {
        int n = a.length;
        long[] b = a.clone(); // 工作数组
        // 正向：b[i] 至少为 b[i-1]-X
        for (int i = 1; i < n; i++) {
            long need = b[i-1] - X;
            if (b[i] < need) b[i] = need;
        }
        // 反向：b[i] 至少为 b[i+1]-X
        for (int i = n - 2; i >= 0; i--) {
            long need = b[i+1] - X;
            if (b[i] < need) b[i] = need;
        }
        long sum = 0L;
        for (int i = 0; i < n; i++) sum += b[i] - a[i];
        return sum;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        for (int tc = 0; tc < T; tc++) {
            // 读 n, k
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            long k = Long.parseLong(st.nextToken());
            // 读数组
            long[] a = new long[n];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());
            // 计算初始最大相邻差
            long R = 0;
            for (int i = 0; i + 1 < n; i++) {
                long d = Math.abs(a[i] - a[i+1]);
                if (d > R) R = d;
            }
            long L = 0;
            // 二分最小可行 X
            while (L < R) {
                long mid = (L + R) >>> 1;
                if (needOps(a, mid) <= k) R = mid;
                else L = mid + 1;
            }
            out.append(L).append('\n');
        }
        System.out.print(out.toString());
    }
}

C++

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

/* 判定给定X是否可行：返回最小所需加法总次数 */
long long need_ops(const vector<long long>& a, long long X) {
    int n = (int)a.size();
    vector<long long> b = a; // 工作数组
    // 正向一趟：右端至少为 左端-X
    for (int i = 1; i < n; ++i) {
        long long need = b[i-1] - X;
        if (b[i] < need) b[i] = need;
    }
    // 反向一趟：左端至少为 右端-X
    for (int i = n - 2; i >= 0; --i) {
        long long need = b[i+1] - X;
        if (b[i] < need) b[i] = need;
    }
    long long sum = 0;
    for (int i = 0; i < n; ++i) sum += b[i] - a[i];
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; long long k;
        cin >> n >> k;
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        long long R = 0;
        for (int i = 0; i + 1 < n; ++i) {
            long long d = llabs(a[i] - a[i+1]);
            if (d > R) R = d;
        }
        long long L = 0;
        // 二分答案
        while (L < R) {
            long long mid = (L + R) / 2;
            if (need_ops(a, mid) <= k) R = mid;
            else L = mid + 1;
        }
        cout << L << "\n";
    }
    return 0;
}

题目内容

小红有一个长度为 $n$ 的数组 $a$ 。

小红可以对数组执行最多 $k$ 次如下操作：

指定数组中的某个元素 $a_i(1≤i≤n)$ ，令 $a_i=a_i+1$ 。对于同一个位置的元素可以多次进行操作。

小红想要最小化数组中相邻元素差的绝对值的最大值，请你帮助他计算。

输入描述

输入包括多组测试数据。

输入第一行有一个正整数 $T(1≤T≤100)$ ，表示测试数据的组数。

对于每组测试数据：

第一行有两个正整数 $n(2≤n≤10^5)$ ，$k(0≤k≤10^9)$ ，分别表示数组的长度、操作最多可以执行多少次。

接下来的一行有 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤10^9)$ ，表示题目给定的数组。

输出描述

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

样例1

输入

1
5 3
3 1 5 4 1

输出

2

说明

其中一种可行的操作为：对第二个元素执行两次操作，对第五个元素执行一次操作，得到新数组 $[3$ $3$ $5$ $4$ $2]$，相邻元素差的绝对值的最大值为 $2$ ，此时最小。