CF2167E khba Loves to Sleep! 题解

sunqihuan · 2025-11-28 15:58:02 · 题解

要求最小值最大，可以想到用二分，二分答案，贪心的放传送门。除了每个人左右答案个长度不能放除外其他全部贪心放满，看看够不够 k 个，最后按照这个方法再做一遍统计答案即可。注意要特判长度为 0 的情况。

代码：

#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;
}