← 返回题目
题库练习 khba Loves to Sleep!
← 上一题 下一题 →

A16744 | khba Loves to Sleep!

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

khba 有 $n$ 个朋友，每个人都站在一条线上，其位置为 $a_i$，且每个人的位置都在 $[0, x]$ 区间内。

他们都想要来到 khba 身边。其中，有一个朋友 Isamatdin 给了 khba $k$ 个传送装置（teleport）。每个人会选择距离自己最近的传送装置（选择距离最近的那个）行走过去。当朋友到达传送装置时，khba 和这个朋友就可以立刻见面。

但是 khba 太累了，在朋友们走过来的时候他会一直睡觉。现在，他希望选择 $k$ 个传送装置的位置，使得这些位置互不相同且都位于区间 $[0,x]$ 内，从而最大化最先到达传送装置的朋友所需要的时间。假设所有朋友的移动速度相同。

由于 khba 不擅长计算，你需要输出选择的 $k$ 个传送装置的位置。

输入格式

每个测试包含多组数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。接下来是各组数据的描述。

每组数据的第一行包含三个整数 $n$，$k$ 和 $x$（$1 \leq n, k \leq 2 \cdot 10^5$，$k-1 \leq x \leq 10^9$）——朋友数量、需要选择的传送装置数量和传送装置可选位置的区间范围。

每组数据的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq x$）——朋友们所在的位置。

保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

保证所有测试数据中 $k$ 的总和不超过 $2 \cdot 10^5$。

输出格式

每组测试用例输出一行，包含 $k$ 个整数，表示所选择的传送装置的位置。这些位置必须互不相同且都在区间 $[0, x]$ 内。输出顺序可以任意。

如果有多种最优方案，可以任选一种输出。

输入输出样例

输入 #1
10
4 1 4
1 0 2 4
5 5 4
0 1 2 3 4
2 1 4
4 0
3 4 6
2 4 3
3 2 12
6 12 0
4 3 12
8 12 0 4
1 1 1000000000
0
1 1 1000000000
1000000000
3 4 9
8 7 9
3 4 9
2 0 1
输出 #1
3 
0 1 2 3 4 
2 
0 1 5 6 
3 9 
2 6 10 
1000000000 
0 
0 1 2 3 
6 7 8 9
C++ 编辑器
输入
输出