CF1904C Array Game

Zinc-Acetate / 2024-01-30 / 原文

题目传送门

codeforces

洛谷

题目大意

给你一个由 $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();
	}
}