CF2167E khba Loves to Sleep! 题解

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int T, n, k, x, a[N], ans[N], cnt;

bool check(int mid)
{
	int p = 0;
	p += max(a[1] - mid + 1, 0) + max(x - a[n] - mid + 1, 0);
	for (int i = 1; i < n; i ++ ) p += max(a[i + 1] - a[i] + 1 - mid * 2, 0);
	return p >= k;
}

void solve()
{
	cnt = 0;
	scanf("%d%d%d", &n, &k, &x);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	int l = 0, r = x;
	while (l < r)
	{
		int mid = (l + r + 1) >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	if (l == 0)
	{
		for (int i = 0; i < k; i ++ ) printf("%d ", i);
		puts("");
		return;
	}
	vector<int> res;
	for (int p = 0; p <= a[1] - l && (int)res.size() < k; p ++ ) res.push_back(p);
	for (int i = 1; i < n && (int)res.size() < k; i ++ )
	{
		int st = a[i] + l, en = a[i + 1] - l;
		for (int p = st; p <= en && (int)res.size() < k; p ++ ) res.push_back(p);
	}
	for (int p = a[n] + l; p <= x && (int)res.size() < k; p ++ ) res.push_back(p);
	int cur = 0;
	while ((int)res.size() < k)
	{
		bool flag = false;
		for (int v : res)
			if (v == cur)
			{
				flag = true;
				break;
			}
		if (!flag) res.push_back(cur);
		cur ++ ;
	}
	for (int i = 0; i < k; i ++ ) printf("%d ", res[i]);
	puts("");
}

int main()
{
	cin >> T;
	while (T -- ) solve();
	return 0;
}