题目描述
难度分:1300
输入T(≤500)表示T组数据。所有数据的n之和≤2000。
每组数据输入n(1≤n≤2000)和长为n的严格递增数组a(1≤a[i]<1018)。
一开始,一维数轴上的所有整点都是白色。
每次操作,你可以选择两个不同的白色整点x和y,满足|x−y|≤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
算法
分类讨论+枚举
分为以下三种情况:
-
如果n=1,由于选择的两个整点一定不相同,所以答案是1。
-
如果n是偶数,那么只能相邻元素两两一对涂黑,取差值的最大值作为答案。
-
如果n是奇数,相当于a中有一个元素可以单独涂黑。枚举这个元素,剩余元素组成一个长度为n−1的数组,而n−1是偶数,用情况2的方法就能求得k,维护k的最小值即可。
复杂度分析
时间复杂度
瓶颈在于n为>1的奇数时,枚举i∈[1,n]还需要构建一个剩余元素组成的数组,然后对这个数组的相邻元素两两组合求k,时间复杂度为O(n)。所以整个算法的时间复杂度为O(n2),利用前后缀分解也可以做到O(n),但是下标的变换比较容易出错,而且n≤2000,O(n2)也是可以接受的,就不写了。
空间复杂度
在n为>1的奇数的情况下,枚举i∈[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;
}