题意 题目链接。 给定 $n$ 个二维欧几里得平面上的点 $p_1, p_2, \dots, p_n$,请输出距离最近的两个点的距离。 解析 在这题下给一篇正经的分治做法,已有的分治做法是用 vector 实现的,可能对于部分同学来说代码实现不便。其他题解都是非分治的。 我们将所有点按照 $x$ 坐标排序后标号为 $1,2,\dots n$,记 $…
题目链接 解析 题意就不多阐述了,看原题就够了。个人觉得这是一道练归并排序性质的好题(虽然动规/堆维护等方法似乎也可行,但我认为最朴素的方法才是最美丽的)。 再发觉贪心不可行时,我们考虑分治维护每一轮比赛可能获胜的人。假设我们以及维护好了左区间(即上一轮比赛)哪些人可能能在上一轮获得胜利(也就是能活到当前这轮)以及右区间的这个信息,我们考虑如何合并…