Array Game
链接：https://codeforces.com/problemset/problem/1904/C
算法：二分+思维
题目简介：
题目描述
给定一个由 $n$ 个正整数组成的数组 $a$。
在一次操作中，您必须选择一对下标 $(i, j)$，满足 $1 \le i < j \le |a|$，并将 $|a_i - a_j|$ 附加到数组 $a$ 的末尾（即数组长度 $n$ 增加 $1$，并将新元素 $a_{new}$ 设置为 $|a_i - a_j|$）。
任务： 在执行恰好 $k$ 次操作后，求数组 $a$ 中所有元素的最小值可能达到的最小是多少，并将其打印出来。
输入
每个测试包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 1000$) —— 测试用例的数量。
每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 2 \cdot 10^3$, $1 \le k \le 10^9$) —— 数组的长度和您应该执行的操作数量。
每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{18}$) —— 数组 $a$ 的元素。
保证所有测试用例中 $n^2$ 的总和不超过 $4 \cdot 10^6$。
输出格式
对于每个测试用例，打印一个整数 —— 即在执行 $k$ 次操作后，数组 $a$ 中所有元素的最小可能值。
前置知识
二分
while(l<r){int mid=l+(r-l)/2;if(a[mid]<=x){l=mid+1;}else{ r=mid; }}
这是找小于等于x的第一个数
while(l<r){int mid=l+(r-l)/2;if(a[mid]>=x){r=mid;}else{ l=mid+1;}}
这是找大于等于x的第一个是数
其实也可以用stl的带的函数
| 你的目标 | 调用的核心代码（获取下标 idx） | ⚠️ 边界防坑指南（极其重要） |
|---|---|---|
| 找第一个 $\ge x$ 的数 | idx = lower_bound(a.begin(), a.end(), x) - a.begin(); |
如果 idx == n，说明数组里所有数都 $< x$。 |
| 找第一个 $> x$ 的数 | idx = upper_bound(a.begin(), a.end(), x) - a.begin(); |
如果 idx == n，说明数组里所有数都 $\le x$。 |
| 找最后一个 $\le x$ 的数 | idx = upper_bound(a.begin(), a.end(), x) - a.begin() - 1; |
必须检查 idx < 0。如果 < 0，说明所有数都 $> x$，没找到。 |
| 找最后一个 $< x$ 的数 | idx = lower_bound(a.begin(), a.end(), x) - a.begin() - 1; |
必须检查 idx < 0。如果 < 0，说明所有数都 $\ge x$，没找到。 |
| 判断 $x$ 是否存在 | auto it = lower_bound(a.begin(), a.end(), x); bool exist = (it != a.end() && *it == x); |
必须先判断 it != a.end() 防越界，再判断值是否相等。 |
| 统计 $x$ 出现的次数 | count = upper_bound(...) - lower_bound(...); |
闭眼用，自带防坑。如果不存在，两者位置重合，相减正好等于 0。 |
做法
情况一：当 $k \ge 3$ 时（抽屉原理/白嫖结论）
- 推导：假设我们在第一次操作中，任意选取了 $a_1$ 和 $a_2$，得到了差值 $v = |a_1 - a_2|$，此时数组里多了一个 $v$。
- 因为同一个元素对可以被重复选取，在第二次操作中，我们再次选取 $a_1$ 和 $a_2$，又得到了一个差值 $v$ 加进数组。
- 此时，数组里存在两个完全相等的元素 $v$。
- 第三次操作，我们直接选取这两个 $v$，计算它们的差值：$|v - v| = 0$。
- 结论：只要操作次数 $\ge 3$，我们必定能捏出一个 $0$。由于元素不能为负，$0$ 就是极限最小值。
- 答案：直接输出 $0$。
情况二：当 $k = 1$ 时（单次博弈）
- 推导：我们只能向数组里塞一个数。最后的最小值只可能诞生于两个地方：
- 数组原本就有的最小值。
- 我们新塞进去的那个差值。
- 为了让新塞进去的差值尽量小，我们需要挑原数组中最接近的两个数相减。
- 做法：将原数组从小到大排序。原数组的最小值就是 $a[0]$。最小的差值必然产生于排序后的相邻元素之间。我们遍历一次数组，找出 $\min(a[i+1] - a[i])$，再和 $a[0]$ 打擂台取最小值即可。
- 复杂度：排序 $O(n \log n)$ + 遍历 $O(n)$。
情况三：当 $k = 2$ 时（本题灵魂：枚举 + 二分）
-
推导：我们可以做两次操作。最优解只可能来自三种情况：
- 两次操作都没能创造出比 $k=1$ 时更小的值（即答案继承 $k=1$ 的结果）。
- 第一次操作产生的差值 $v$，直接就是全局最小了。
- 最关键的情况：利用第一次操作产生的差值 $v$，在第二次操作时，让它与原数组中的某个元素 $a_m$ 相减，即制造出 $|v - a_m|$，这个值可能是最小的。
-
怎么做？
- 首先，把数组排序。
- 利用两层
for循环，暴力枚举第一次操作的所有可能结果：$v = a[j] - a[i]$（其中 $j > i$）。这一步是 $O(n^2)$。 - 对于每一个枚举出的 $v$，我们需要在原数组中找一个离它最近的元素 $a_m$，使得 $|v - a_m|$ 最小。
- 既然数组已经排好序，找最近元素直接上二分！使用
lower_bound查找 $v$。- 它会返回第一个 $\ge v$ 的元素所在的位置（它的右邻居）。
- 它的前一个位置，就是最后一个 $< v$ 的元素（它的左邻居）。
- 分别计算 $v$ 与左邻居、右邻居的差值，更新全局最小值。
-
复杂度：外层两层循环 $O(n^2)$，内层二分 $O(\log n)$，总时间复杂度 $O(n^2 \log n)$。$2000^2 \times 11 \approx 4.4 \times 10^7$ 次运算，完美跑进时限。
(AI写的，我表达能力太差了，给了思路，剩下都是他写的，AI就是好用哈，我们会不会都被AI替代？)
贴个代码，码风有点差
https://codeforces.com/contest/1904/submission/367454926