# E. khba Loves to Sleep! [문제 링크](https://codeforces.com/contest/2167/problem/E) ## Problem Statement khba has $n$ friends, each standing on a line at position $a_i$, and each of them is in the range $[0, x]$. They all want to come to him. One of his friends, Isamatdin, gave him $k$ teleports. Each friend will walk to the nearest teleport (choosing the shortest distance). Once a friend reaches a teleport, khba and the friend can instantly meet. But khba is so tired that he'll be sleeping while his friends are walking toward him. Now he wants to choose $k$ teleport positions so that their positions are distinct and lie within the range $[0, x]$, in order to maximize the time it takes for the first friend who reaches a teleport to reach it. Assume that friends move at the same speed. Since khba isn't good at calculations, you should output the $k$ chosen teleport positions. ## Input Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows. The first line of each test case contains three integers $n$, $k$, and $x$ ($1 \le n, k \le 2 \cdot 10^5$, $k - 1 \le x \le 10^9$) — the number of friends, the number of teleports, and the range of possible positions for the teleports. The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le x$) — the positions of khba's friends. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. It is guaranteed that the sum of $k$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each test case, output a single line containing $k$ integers — the $k$ chosen teleport positions. The positions must be distinct and lie within the range $[0, x]$. The positions may be output in any order. If there are multiple optimal choices, output any of them. ## 풀이 매개변수 탐색을 이용하여 최소 거리 x를 찾아주었습니다. ``` c++ #include<bits/stdc++.h> using namespace std; int a[200002]; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n, k, x; cin >> n >> k >> x; for(int i=0;i<n;i++) cin >> a[i]; sort(a, a+n); int left=0, right=x; while(left<right) { int mid = left+right+1>>1; int cnt = max(0, a[0]-mid+1) + max(0, x-a[n-1]-mid+1); for(int i=0;i<n-1;i++) cnt += max(0, a[i+1]-a[i]-2*mid+1); if(cnt>=k) left=mid; else right=mid-1; } int i=0, cnt=0, pos=0; while(cnt<k) { if(i==n) { if(pos-a[n-1]>=left) { cnt++; cout << pos << ' '; } pos++; } else { if(a[i]-pos>=left) { cnt++; cout << pos << ' '; pos++; } else { if(left) pos = a[i]+left; i++; } } } cout << '\n'; } } ```