4028: KNN
内存限制：128 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：171
解决：47
题目描述
KNN算法是机器学习中最简单的算法之一，可以用来回归和分类
在回归模型中，通过找出一个样本的k个最近邻居，将这些邻居的某个属性的平均值赋给该样本，就可以得到该样本的预测值
这个问题可以转化为，求空间中距离样本点最近的k个点的平均值来解决
现在给出确定的k，同时有n个点，给出每个点到样本点的距离和这个点的值，请求出按给出顺序添加到第i个点时，样本点的预测值，当前添加的点数不足k个时只需计算当前平均值
规定距离样本点同样距离时，优先取值较小的点
结果保留两位小数
在回归模型中，通过找出一个样本的k个最近邻居，将这些邻居的某个属性的平均值赋给该样本，就可以得到该样本的预测值
这个问题可以转化为，求空间中距离样本点最近的k个点的平均值来解决
现在给出确定的k，同时有n个点，给出每个点到样本点的距离和这个点的值，请求出按给出顺序添加到第i个点时，样本点的预测值，当前添加的点数不足k个时只需计算当前平均值
规定距离样本点同样距离时，优先取值较小的点
结果保留两位小数
输入
第一行两个用空格隔开的数n和k(1<=n<=2e5,1<=k<=20)
第二行n个整数，第i个数为di，表示第i个给出的点到样本点的距离(0<=di<=1e9)
第三行n个整数，第i个数为ai，表示第i个给出的点的值(0<=ai<=1000)
第二行n个整数，第i个数为di，表示第i个给出的点到样本点的距离(0<=di<=1e9)
第三行n个整数，第i个数为ai，表示第i个给出的点的值(0<=ai<=1000)
输出
输出一行n个浮点数，用空格隔开，表示第按给出顺序添加到第i个点时样本点的预测值
注: 输出末尾无空格
结果保留两位小数
注: 输出末尾无空格
结果保留两位小数
样例输入 复制
6 3
5 5 5 1 6 3
9 8 7 6 5 4
样例输出 复制
9.00 8.50 8.00 7.00 7.00 5.67
提示
样例解释:
添加前3个点时，由于点数没有超过k于是只需直接计算平均值，添加到第4个点时，第4个点距离样本点距离最小，前3个点距离样本点距离相同，于是取值较小的点，样本点最近的k个邻居为第2,3,4个点
添加第5,6个点时同理
添加前3个点时，由于点数没有超过k于是只需直接计算平均值，添加到第4个点时，第4个点距离样本点距离最小，前3个点距离样本点距离相同，于是取值较小的点，样本点最近的k个邻居为第2,3,4个点
添加第5,6个点时同理