题目传送门
题目大意
给你一个由 \(n\) 个正整数组成的数组 \(a\) 。在一次操作中，选取 \((i, j)\) ，将 \(|a_i - a_j|\) 加到 \(a\) 的末尾。你的任务是在执行 \(k\) 操作后，最小化最后数组 \(a\) 的最小值。
思路
分三种情况：
-
\(k \geq 3\) 时，我们可以取两次相同的 \(|a_i - a_j|\) ，这样数组中就会出现两个相同的数，第三次操作取这两个相同的数即可，可以保证最小值为 \(0\) ；
-
\(k=1\) 时，我们暴力枚举每组 \(|a_i - a_j|\) ，然后直接取数组 \(a\) 和枚举出的每组 \(|a_i - a_j|\) 的最小值；
-
\(k=2\) 时，我们考虑先暴力枚举出每组 \(|a_i - a_j|\) ，并对原数组 \(a\) 排序，对于每个得到的 \(|a_i - a_j|\) ，在排好序的原数组 \(a\) 中二分找到与这个值最接近的数，和它取差值，最后答案就是原数组 \(a\) 、暴力枚举出每个 \(|a_i - a_j|\) 、二分找到的数取的差值，这三组数中的最小值。
最坏情况时间复杂度 \(O(n^{2}\log{n})\) ，可以接受。
代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
if (k >= 3)
{
cout << 0 << endl;
return;
}
int minn = LLONG_MAX;
for (int i = 0; i < n; i++)
{
minn = min(minn, a[i]);
}
vector<int> b;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
int c = abs(a[i] - a[j]);
b.push_back(c);
minn = min(minn, c);
}
}
if (k == 1)
{
cout << minn << endl;
return;
}
sort(a.begin(), a.end());
for (auto i : b)
{
int l = 0, r = n - 1, mid, d = 0;
while (l <= r)
{
mid = (l + r) >> 1;
if (a[mid] <= i)
{
l = mid + 1;
d = mid;
}
else
{
r = mid - 1;
}
}
minn = min(minn, abs(a[d] - i));
if (d != n - 1)
minn = min(minn, abs(a[d + 1] - i));
}
cout << minn << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
}