题目描述

难度分:$1400$

输入$T(\leq 1000)$表示$T$组数据。所有数据的$n^2$之和$\leq 4 \times 10^6$。

每组数据输入$n(2 \leq n \leq 2 \times 10^3)$、$k(1 \leq k \leq 10^9)$和长为$n$的数组$a(1 \leq a[i] \leq 10^{18})$。

每次操作，你可以选择两个不同的下标$i$和$j$，然后把$|a[i]-a[j]|$加到$a$的末尾。

输出操作$k$次后，$min(a)$的最小值。

输入样例

4
5 2
3 9 7 15 1
4 3
7 4 15 12
6 2
42 47 50 54 62 79
2 1
500000000000000000 1000000000000000000

输出样例

1
0
3
500000000000000000

算法

找规律+枚举

先找规律，如果$k \geq 3$答案肯定就是$0$，因为可以两次都选一模一样的$(i,j)$，这样就能得到两个相等的数。

如果$k=1$，那么答案要么是$a[1]$，要么是一次操作能够得到的新元素。即$a[1]$和$min_{i \in [1,n],j \in [1,n],i \neq j}|a[j]-a[i]|$中的较小值。

如果$k=2$，则$O(n^2)$枚举第一次加进去的数$delta=|a[j]-a[i]|$，第二次操作如果选到了$delta$，肯定就要选距离$delta$最近的数，事先将$a$排序，然后$O(log_2n)$二分找到就可以求出来这种情况的最小值。如果第二次操作选到的是加入$delta$之前原数组中的数对，那答案就是$min_{i \in [1,n],j \in [1,n],i \neq j}|a[j]-a[i]|$。

复杂度分析

时间复杂度

最差情况是$k=2$的时候，需要对数组先排序，时间复杂度为$O(nlog_2n)$。然后$O(n^2)$枚举第一次操作所加入的元素$delta=|a[j]-a[i]|$，对每个$delta$我们还要在原数组$a$中二分找到离它最近的元素，时间复杂度为$O(log_2n)$。因此，整个算法的时间复杂度为$O(n^2log_2n)$。

空间复杂度

除了输入的数组$a$，仅使用了有限几个变量，因此额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2010;
int T, n, k;
LL a[N];

void solve() {
    sort(a + 1, a + n + 1);
    LL ans = a[2] - a[1];
    for(int i = 2; i <= n; i++) {
        ans = min(ans, a[i] - a[i - 1]);
    }
    for(int i = 1; i < n; i++) {
        for(int j = i + 1; j <= n; j++) {
            LL delta = a[j] - a[i];
            int k = lower_bound(a + 1, a + n + 1, delta) - a;
            if(k <= n && a[k] == delta) {
                puts("0");
                return;
            }else {
                ans = min(ans, a[k] - delta);
                if(k > 1) {
                    k--;
                    ans = min(ans, delta - a[k]);
                }
            }
        }
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
        }
        if(k >= 3) {
            puts("0");
        }else if(k == 2) {
            solve();
        }else {
            sort(a + 1, a + n + 1);
            LL ans = a[1];
            for(int i = 2; i <= n; i++) {
                ans = min(ans, a[i] - a[i - 1]);
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}