首页 > 代码库 > BestCoder9 1003 Revenge of kNN(hdu 4995) 解题报告
BestCoder9 1003 Revenge of kNN(hdu 4995) 解题报告
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4995
题目意思:在一个一维坐标轴上,给出位置 xi 和值 vi,对于 M 次询问,每次询问给出index Qi,求出离数组下标 Qi(从1开始) 最近的 K 个点,从新计算该下标所指示的value值,即等于 K 个 最近点的value值之和 / K,如果有多个K的最近点,那么选择坐标值靠前的那组。
模拟题。首先对将位置从小到大排序,然后求出每一个点的 K 个最近点,最近是通过xi 离当前 xpos 的距离来判断的,不断试探。如果发现左边的点的xl 比 右边的的点 xr 离 xi的距离近,那么就选左边的点。
这个代码是学人家的,自以为看懂,写起来还是反反复复修改了很多次才成功~~~
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 #include <vector> 7 using namespace std; 8 9 typedef __int64 LL;10 const int maxn = 1e5 + 5;11 double vi[maxn];12 vector<int> g[maxn];13 int N, M, K;14 15 struct node16 {17 int id, xi;18 }point[maxn];19 20 int cmp(const node& a, const node& b)21 {22 return a.xi < b.xi;23 }24 25 bool Judge(int pos, int l, int r)26 {27 if (r > N)28 return true;29 if (l <= 0)30 return false;31 if (point[pos].xi - point[l].xi != point[r].xi - point[pos].xi) // 离两边距离值不同,选择距离值更小的那个点32 return point[pos].xi - point[l].xi < point[r].xi - point[pos].xi;33 return point[l].id < point[r].id; // 如果离两边的距离值相同,那么选择坐标值小的那个34 }35 36 void Get_KNN(int pos) // 获得每个点的最近 k 个点是那些37 {38 int id = point[pos].id;39 int l = pos - 1, r = pos + 1;40 for (int i = 0; i < K; i++) 41 {42 if (Judge(pos, l, r))43 g[id].push_back(point[l--].id);44 else45 g[id].push_back(point[r++].id);46 }47 }48 49 int main()50 {51 int T;52 while (scanf("%d", &T) != EOF)53 {54 while (T--)55 {56 scanf("%d%d%d", &N, &M, &K);57 for (int i = 1; i <= N; i++)58 {59 scanf("%d%lf", &point[i].xi, &vi[i]);60 point[i].id = i;61 }62 sort(point+1, point+1+N, cmp);63 for (int i = 1; i <= N; i++)64 Get_KNN(i);65 int ask;66 double ans = 0;67 for (int i = 0; i < M; i++)68 {69 scanf("%d", &ask);70 double sum = 0;71 for (int j = 0; j < g[ask].size(); j++)72 sum += vi[g[ask][j]];73 vi[ask] = sum / K;74 ans += vi[ask];75 }76 printf("%.6lf\n", ans);77 for (int j = 1; j <= N; j++)78 g[j].clear();79 }80 }81 return 0;82 }
BestCoder9 1003 Revenge of kNN(hdu 4995) 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。