hdu 4347 The Closest M Points (kd-tree+优先队列,求M近邻)

题目链接

题意:

给出若干个点,在给出一个定点,求距离该定点最近的m个点。

思路:

我们已经知道kd-tree可以得到最近邻,实际上M近邻,只需要维护一个size为M的优先队列就可以了。

需要注意,优先队列的元素一定要先定义小于关系orz

以及这次采用了轮盘转的策略划分维度,也就是按照深度,所有维度轮流作为split-method(实际用起来效果还是挺棒的orz

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz