hdu 4995(离散化下标+模拟)
Revenge of kNN
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 584 Accepted Submission(s): 136
pattern recognition, the k-Nearest Neighbors algorithm (or k-NN for
short) is a non-parametric method used for classification and
regression. In both cases, the input consists of the k closest training
examples in the feature space.
In k-NN regression, the output is the
property value for the object. This value is the average of the values
of its k nearest neighbors.
---Wikipedia
Today, kNN takes
revenge on you. You have to handle a kNN case in one-dimensional
coordinate system. There are N points with a position Xi and value Vi.
Then there are M kNN queries for point with index i, recalculate its
value by averaging the values its k-Nearest Neighbors. Note you have to
replace the value of i-th point with the new calculated value. And if
there is a tie while choosing k-Nearest Neighbor, choose the one with
the minimal index first.
Each
test case begins with three integers N, M and K, in which K indicating
the number of k-Nearest Neighbors. Then N lines follows, each line
contains two integers Xi and Vi. Then M lines with the queried index Qi
follows.
[Technical Specification]
1. 1 <= T <= 5
2. 2<=N<= 100 000, 1<=M<=100 000
3. 1 <= K <= min(N – 1, 10)
4. 1 <= Vi <= 1 000
5. 1 <= Xi <= 1 000 000 000, and no two Xi are identical.
6. 1 <= Qi <= N
5 3 2
1 2
2 3
3 6
4 8
5 8
2
3
4
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = ;
struct Node{
LL x;
int id1;
double v;
}node[N];
int idx[N];
int cmp(Node a,Node b){
return a.x<b.x;
}
int main()
{
int tcase,n,m,k,x;
scanf("%d",&tcase);
while(tcase--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++){
scanf("%lld%lf",&node[i].x,&node[i].v);
node[i].id1 = i;
}
sort(node+,node++n,cmp);
for(int i=;i<=n;i++){
idx[node[i].id1] = i;
}
double sum = ;
while(m--){
int id;
scanf("%d",&id);
int now = idx[id];
double avg = ;
int l = now-,r = now+;
for(int i=;i<=k;i++){
if(l>=&&r<=n){
LL dis1 = node[now].x - node[l].x;
LL dis2 = node[r].x - node[now].x;
if(dis1<dis2){
avg+=node[l--].v;
}else if(dis1>dis2){
avg+=node[r++].v;
}else { ///相等的话按照邻居原来的下标进行选择
int ori_l = node[l].id1;
int ori_r = node[r].id1;
if(ori_l<ori_r) {
avg+=node[l--].v;
}else{
avg+=node[r++].v;
}
}
}else if(l>=){
avg+=node[l--].v;
}else if(r<=n){
avg+=node[r++].v;
}
}
/* ///不知道WA的原因
int l=1,r=1;
for(int i=1;i<=k;i++){
if(now-l>=1&&now+r<=n){
LL dis1 = node[now].x - node[now-l].x;
LL dis2 = node[now+r].x - node[now].x;
if(dis1<dis2){
avg+=node[now-l].v;
l++;
}else if(dis1>dis2){
avg+=node[now+r].v;
r++;
}else { ///相等的话按照邻居原来的下标进行选择
int ori_l = node[now+l].id1;
int ori_r = node[now+r].id1;
if(ori_l<ori_r) {
avg+=node[now-l].v;
l++;
}else{
avg+=node[now+r].v;
r++;
}
}
}else if(now-l>=1){
avg+=node[now-l].v;
l++;
}else if(now+r<=n){
avg+=node[now+r].v;
r++;
}
}*/
node[now].v = avg/k;
sum+=avg/k;
}
printf("%.6lf\n",sum);
}
return ;
}
最新文章
- 深入理解JSONP原理——前端面试
- .NET涉及的一些名词
- iOS-SDWebImage
- SQL Server 2008 评估期已过解决方法
- ServiceStack
- css3 text-transform变形动画
- WordPress社会化评论插件多说、有言、灯鹭、评论啦
- PHP中$_GET['name']与$_POST['name']变量直接用变量名$name的php配置
- Swift学习笔记（一）搭配环境以及代码运行成功
- 在hive中直接对timestamp类型取max报错
- dirlock.go
- .net 使用oracle 的存储过程有返回值也有数据集（游标）
- LeetCode（65）：有效数字
- HUAWEI USG6000系列 & NGFW Module V100R001 典型配置案例
- TFS 报错解决方案:tf400324
- k8s weave network IP回收冲突
- ArcGIS案例学习笔记2_1_山顶点提取最大值提取
- iOS常用代码总结
- 如何获取 docker 容器(container)的 ip 地址
- Spring Boot(十二)：Spring Boot 如何测试打包部署