hdu 5992 Finding Hotels kd树

缘起

最近开始研究机器学习中的一些算法. 首先拿 KNN 算法（即k邻近算法）开刀. 但是KNN基于kd树. 而kd树我刚好做过一道题【1】(QAQ)，遂打算加强一下kd树的素养. 所以打算多找几道题练习加深理解一下kd树.

hdu 5992 Finding Hotels

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
有N个旅馆, 每个旅馆有坐标位置和价格. M个旅客想要在可接受的价格范围内找一个最近的旅馆.
距离的度量采用欧式度量.

【输入】
多样例. 第一行是样例数. 对每个样例，首先是N（N ≤ 200000），然后是M（M ≤ 20000）. 然后N行
每行描述的是一个旅馆. 一行三个整数.x (1 ≤ x ≤ N), y (1 ≤ y ≤ N) and c (1 ≤ c ≤ N)
x,y是旅馆的坐标. c是价格. 输入保证不同的旅馆有不同的x, 不同的y, 不同的c. 然后是M行，每行刻画一个
旅客. 也是每行三个整数. x (1 ≤ x ≤ N), y (1 ≤ y ≤ N) and c (1 ≤ c ≤ N),
其中(x,y)是旅客的坐标. c是该旅客最多能支付的价格.

【输出】
对每个顾客的询问，输出他可以接受的离他最近的旅店的xyz. 如果有多个, 输出编号最小的那一个

【样例输入】
2
3 3
1 1 1
3 2 3
2 3 2
2 2 1
2 2 2
2 2 3
5 5
1 4 4
2 1 2
4 5 3
5 2 1
3 3 5
3 3 1
3 3 2
3 3 3
3 3 4
3 3 5

【样例输出】
1 1 1
2 3 2
3 2 3
5 2 1
2 1 2
2 1 2
1 4 4
3 3 5

【限制】
1s

本题其实和【1】十分的像——都只涉及kd树的构建和查询. 对每组数据, 首先使用旅馆数据(就是kd树的节点)构建2维kd树. 然后对每个旅客就是目标点. 然后使用【1】中的搜索模板, 唯一与【1】不同的地方在于加入大根堆的条件还需要价格可接受.

所以使用【1】中的模板虐之~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 200005, k=2; // 2维kd树
int n,m,depth,ans; // input[ans]是对每个顾客而言最佳的旅店, ans_dis是它到此顾客的距离
typedef long long LL;
LL ans_dis;
#define SQUARE(x) ((x)*(x))

struct KdTreeNode
{
	LL x[k];
	int price, index; // x[2]是节点的坐标, price是价格, index是在input中的编号(因为最后要求多个满足的话,输出下标最小的那个)
	bool flag; // 是否是kd树的节点（因为kd树不是完全二叉树, 节点与节点之间的数组元素可能不是kd树的节点）, 这用于递归出口
	bool operator<(const KdTreeNode &o) const
	{
		return x[depth]<o.x[depth]; // 注意, 这个operator不是给大根堆用的(大根堆唯一的标准就是目标节点的距离,虽然本题没有大根堆),而是给nth_element用的, 因为构建kd树的时候想将中垂线居左的点放在kd树左边,中锤线居右的点放在kd树右边
	}
}kdTree[maxn<<2], input[maxn];

void build(int begin, int end, int cur, int dep) // 和线段树的构建极为类似
{
	if (begin>end) return;
	depth = dep%k;
	int mid = (begin+end)>>1;
	nth_element(input+begin, input+mid, input+end+1);
	kdTree[cur] = input[mid];
	kdTree[cur].flag = true;
	build(begin, mid-1, cur<<1, dep+1);
	build(mid+1, end, cur<<1|1, dep+1);
}

void query(KdTreeNode &target, int cur, int dep)
{
	KdTreeNode curNode = kdTree[cur]; // 当前节点
	if (!curNode.flag) return; // 本节点不是数据节点
	if (curNode.price<=target.price) // 检查当前节点
	{
		LL dis=SQUARE(curNode.x[0]-target.x[0])+SQUARE(curNode.x[1]-target.x[1]);
		if (!ans || dis<ans_dis || (dis==ans_dis  && kdTree[cur].index<kdTree[ans].index)) // 要么是第一次, 要么是严格小, 要么就是相等,但是下标小
		{
			ans = cur;
			ans_dis = dis;
		}
	}
	int tx = target.x[dep%k]< curNode.x[dep%k]?(cur<<1):(cur<<1|1); // 如果目标节点在当前节点左侧的话, 这个左右关系就是在构建kd树的时候通过nth_element确定的
	int ty = tx^1;
	query(target, tx, dep+1); // 搜索target所在的一侧
	if (SQUARE(target.x[dep%k]-curNode.x[dep%k]) <= ans_dis) // 注意,<=就有必要搜另一侧, 因为要输出下标最小的那个. 上面仅仅搜了target所在的curNode的一侧
	{
		query(target, ty, dep+1); // 搜索target的另一侧
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		memset(kdTree, 0, sizeof(kdTree)); // 清空flag
		scanf("%d%d", &n,&m);
		for (int i = 1; i<=n; i++)
		{
			scanf("%lld%lld%d", &input[i].x[0],&input[i].x[1], &input[i].price);
			input[i].index =i;
		}
		build(1,n,1,0);
		KdTreeNode target;
		while(m--)
		{
			scanf("%lld%lld%d", &target.x[0], &target.x[1], &target.price);
			ans=0, ans_dis = 1LL<<60; // 初始化
			query(target,1,0);
			printf("%lld %lld %d\n",kdTree[ans].x[0], kdTree[ans].x[1], kdTree[ans].price);
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 312ms
Memory 23912kB
Length 2378
Lang G++
Submitted 2019-09-22 16:24:40
Shared
RemoteRunId 30675090

其实你不觉得这是高德地图等一众APP中智能排序的雏形吗? ^_^

参考

【1】https://yfsyfs.github.io/2019/06/03/hdu-4347-The-Closest-M-Points-KD%E6%A0%91-k-%E9%82%BB%E8%BF%91%E7%AE%97%E6%B3%95/