首页 > 代码库 > HDU - 4995 - Revenge of kNN
HDU - 4995 - Revenge of kNN
题目链接 : https://vjudge.net/problem/HDU-4995
题目大意 : 读入n个点的坐标与该点所拥有的值val,进行m次查询,对于每一次查询,读入该点的坐标,计算离该点最近的k个点的值(距离相同的索引小的优先),进行求和求平均,
然后更新改点的值,最后输出更新的值的和。
题目分析 : 一个比较不错的模拟的题目,可以对坐标值和 索引进行hash来优化计算时间。
其他进行模拟即可,注意读入的值并不是有序的,需要先进行排序。
代码实现 :
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 #include <algorithm> 5 #include <cstdio> 6 using namespace std; 7 int m,n,k; 8 struct node 9 { 10 double point; 11 double val; 12 int id; 13 }; 14 bool comp(const node &a,const node& b) 15 { 16 return a.point<b.point; 17 } 18 int hashs[110000+10]; 19 node nodes[110000+10]; 20 void init() 21 { 22 cin>>n>>m>>k; 23 for(int i=0;i<n;i++) 24 { 25 double a; 26 double b; 27 scanf("%lf%lf",&a,&b); 28 nodes[i].point=a; 29 nodes[i].val=b; 30 nodes[i].id = i; 31 } 32 sort(nodes,nodes+n,comp); 33 for(int i=0;i<n;i++) 34 { 35 hashs[nodes[i].id+1]=i; 36 } 37 } 38 double solve() 39 { 40 double SUM=0; 41 for(int i=0;i<m;i++) 42 { 43 int t; 44 scanf("%d",&t); 45 // cout<<t<<endl; 46 int mid=hashs[t]; 47 int l=mid-1,r=mid+1; 48 int K=k; 49 double sum=0; 50 while(K--) 51 { 52 if(l>=0&&r<n) 53 { 54 double d1=nodes[l].point; 55 double d2=nodes[r].point; 56 double t1=nodes[mid].point-d1; 57 double t2=d2-nodes[mid].point; 58 // cout<<t1<<" "<<t2<<" "<<"*"<<endl; 59 if(t1<t2) 60 { 61 sum+=nodes[l].val; 62 // cout<<nodes[l].val<<" "<<l<<endl; 63 l--; 64 } 65 else if(t1>t2) 66 { 67 sum+=nodes[r].val; 68 // cout<<nodes[r].val<<" "<<r<<endl; 69 r++; 70 }else if(t1==t2) 71 { 72 if(nodes[l].id<nodes[r].id) 73 { 74 sum+=nodes[l].val; 75 l--; 76 } 77 else 78 { 79 sum+=nodes[r].val; 80 r++; 81 } 82 } 83 } 84 else if(l>=0) 85 { 86 sum+=nodes[l].val; 87 // cout<<nodes[l].val<<" "<<l<<endl; 88 l--; 89 }else if(r<n) 90 { 91 sum+=nodes[r].val; 92 // cout<<nodes[r].val<<" "<<r<<endl; 93 r++; 94 } 95 } 96 // cout<<sum<<" *"<<endl; 97 sum=sum/k; 98 //cout<<sum<<endl; 99 SUM+=sum; 100 nodes[mid].val=sum; 101 } 102 return SUM; 103 } 104 int main() 105 { 106 int T; 107 cin>>T; 108 while(T--) 109 { 110 init(); 111 double sum=solve(); 112 printf("%.6lf\n",sum); 113 } 114 return 0; 115 }
HDU - 4995 - Revenge of kNN
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。