U229850 [sxyz NOIP 模拟赛]2 第 k 个数（kth）

[sxyz NOIP 模拟赛]2 第 k 个数（kth）T2 ------------ 2s 512MB

给定 n 个整数 ai 你会通过如下方式得到一个长度为 $\dfrac{n∗(n−1)}{2}$ 的数组：枚举所有不同的 i, j(i < j)，将|ai − aj | 加入数组中，最后将数组按照从小到大的顺序排序。 你需要求出，这个数组的第 k 个数字是多少

第一行两个整数 n, k 第二行 n 个整数 ai

一行一个整数，表示数组的第 k 个元素

2.4 数据范围与提示 对于 30% 的数据，n ≤ $10^3$ 对于 70% 的数据，k ≤ $10^5$ 对于所有数据，1 ≤ n ≤ $10^5$, 1 ≤ k ≤ $\dfrac{n∗(n−1)}{2}$ , 1 ≤ ai ≤ $10^9$ 注意 k 的大小可能会超过 32 位整数能表示的范围