CF2167E题解

Entropy_Lyu · 2025-11-18 16:27:54 · 题解

思路

最大化首个朋友到达传送点的时间，二分答案找最大可能的最小距离 d。

对每个 d，计算朋友需覆盖的区间并合并，判断剩余空位能否放 k 个传送点。

确定 d 后，从合并区间外的空位中选 k 个位置作为传送点。

代码

#include<bits/stdc++.h>
#define int long long
#define ft first
#define sd second
using namespace std;
int read(){
    int cnt = 0, sign = 1;
    char c = getchar();
    while(!isdigit(c)){
        if(c == '-')    sign = -1;
        c = getchar();
    }
    while(isdigit(c)){
        cnt = (cnt << 1) + (cnt << 3) + (c ^ 48);
        c = getchar();
    }
    return cnt * sign;
}
const int N = 2e5 + 10;
int a[N]; 
signed main(){
    int T = read();
    while(T--){
        int n = read(), k = read(), x = read();
        for(int i = 1; i <= n; i++){
            a[i] = read();
        }
        sort(a + 1, a + n + 1);
        int l = 0, r = x + 2;
        while(l <= r){
            int mid = (l + r) >> 1;
            vector < pair <int, int> > vec;
            for(int i = 1; i <= n; i++){
                int lt = max(a[i] - mid + 1, 0ll);
                int rt = min(a[i] + mid - 1, x * 1ll);
                if(lt <= rt)    vec.push_back({lt, rt});
            }
            sort(vec.begin(), vec.end());
            vector < pair <int, int> > mer;
            for(auto &t : vec){
                if(mer.empty() || t.ft > mer.back().sd + 1){
                    mer.push_back(t);
                }else{
                    mer.back().sd = max(mer.back().sd, t.sd);
                }
            }
            int sum = 0;
            for(auto &t : mer){
                sum += (t.sd - t.ft + 1);
            }
            if(x + 1 - sum >= k){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        vector < pair <int, int> > vec;
        int de = r;
        for(int i = 1; i <= n; i++){
            int lt = max(a[i] - de + 1, 0ll);
            int rt = min(a[i] + de - 1, x * 1ll);
            if(lt <= rt)    vec.push_back({lt, rt});
        }
        sort(vec.begin(), vec.end());
        vector < pair <int, int> > mer;
        for(auto &t : vec){
            if(mer.empty() || t.ft > mer.back().sd + 1){
                mer.push_back(t);
            }else{
                mer.back().sd = max(mer.back().sd, t.sd);
            }
        }
        vector <int> ans;
        int cnt = 0;
        for(auto &t : mer){
            for(int i = cnt; i < t.ft && ans.size() < k; i++){
                ans.push_back(i);
            }
            cnt = t.sd + 1;
            if(ans.size() >= k){
                break;
            }
        }
        if(ans.size() < k){
            for(int i = cnt; i <= x && ans.size() < k; i++){
                ans.push_back(i);
            }
        }
        for(int i = 0; i < k; i++){
            printf("%d ", ans[i]);
        }
        printf("\n");
    }
    return 0;
}