题目描述

难度分:$1300$

输入$T(\leq 500)$表示$T$组数据。所有数据的$n$之和$\leq 2000$。

每组数据输入$n(1 \leq n \leq 2000)$和长为$n$的严格递增数组$a(1 \leq a[i] \lt 10^{18})$。

一开始，一维数轴上的所有整点都是白色。

每次操作，你可以选择两个不同的白色整点$x$和$y$，满足$|x-y| \leq k$，然后把这两个白色整点涂黑。注意$x$和$y$不一定要在$a$中。

你需要把在$a$中的整点全部涂黑。此外，最多有一个不在$a$中的整点也可以涂黑。

输出$k$的最小值。

输入样例

4
2
1 2
1
7
3
2 4 9
5
1 5 8 10 13

输出样例

1
1
2
3

算法

分类讨论+枚举

分为以下三种情况：

1. 如果$n=1$，由于选择的两个整点一定不相同，所以答案是$1$。

2. 如果$n$是偶数，那么只能相邻元素两两一对涂黑，取差值的最大值作为答案。

3. 如果$n$是奇数，相当于$a$中有一个元素可以单独涂黑。枚举这个元素，剩余元素组成一个长度为$n-1$的数组，而$n-1$是偶数，用情况$2$的方法就能求得$k$，维护$k$的最小值即可。

复杂度分析

时间复杂度

瓶颈在于$n$为$\gt 1$的奇数时，枚举$i \in [1,n]$还需要构建一个剩余元素组成的数组，然后对这个数组的相邻元素两两组合求$k$，时间复杂度为$O(n)$。所以整个算法的时间复杂度为$O(n^2)$，利用前后缀分解也可以做到$O(n)$，但是下标的变换比较容易出错，而且$n \leq 2000$，$O(n^2)$也是可以接受的，就不写了。

空间复杂度

在$n$为$\gt 1$的奇数的情况下，枚举$i \in [1,n]$时，对每个$i$还需要用剩余的$n-1$个元素构建一个新的数组，所以需要$O(n)$的额外空间，这也是整个算法的额外空间复杂度。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 2010;
int T, n;
LL a[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
        }
        if(n == 1) {
            puts("1");
        }else {
            if(n % 2 == 0) {
                LL ans = a[2] - a[1];
                for(int i = 4; i <= n; i += 2) {
                    ans = max(ans, a[i] - a[i - 1]);
                }
                printf("%lld\n", ans);
            }else {
                LL ans = 1e18;
                for(int i = 1; i <= n; i++) {
                    LL k = 0;
                    vector<LL> arr;
                    for(int j = 1; j <= n; j++) {
                        if(j != i) arr.push_back(a[j]);
                    }
                    for(int j = 1; j < arr.size(); j += 2) {
                        k = max(k, arr[j] - arr[j - 1]);
                    }
                    ans = min(ans, k);
                }
                printf("%lld\n", ans);
            }
        }
    }
    return 0;
}