首页 > 代码库 > HDU4995Revenge of kNN(暴力)
HDU4995Revenge of kNN(暴力)
题目:HDU4995Revenge of kNN(暴力)
题目大意:给你一维的N个点,每个点有X坐标,和V值,然后现在给你M个修改,接下来的M行每行给你一个Qi(前面的N个点的序号1--N)。要求每次取离X(Qi)最近的K个邻居,然后将X(Qi)的值改为(这K个邻居的值的平均值),最后输出这M次修改值的和。如果距离相同的话就取原先读入下标小的那个邻居。
解题思路:先将这N个点按照X的值排序 + 暴力。Qi是下标不是X,这个没看清楚,坑死了。
代码:
#include <cstdio> #include <cstring> #include <algorithm> #include <map> using namespace std; const int N = 1e5 + 5; typedef long long ll; map<int, int> vis; int T, n, m, k; struct Node { ll x; double v; int id; }node[N]; int cmp (const Node &a, const Node &b) { return a.x < b.x; } double solve () { double ans = 0; vis.clear(); sort (node, node + n, cmp); for (int i = 0; i < n; i++) vis[node[i].id] = i; int pos, tmp; int num; for (int i = 0; i < m; i++) { scanf ("%d", &num); pos = vis[num - 1]; // printf ("%d\n", pos); int p1 = pos - 1; int p2 = pos + 1; double sum = 0; tmp = 0; while (tmp < k) { if (p1 == -1)//边界要注意 sum += node[p2++].v; else if (p2 == n)//边界 sum += node[p1--].v; else { if (node[pos].x - node[p1].x < node[p2].x - node[pos].x) sum += node[p1--].v; else if (node[pos].x - node[p1].x > node[p2].x - node[pos].x) sum += node[p2++].v; else if (node[p1].id < node[p2].id) sum += node[p1--].v; else sum += node[p2++].v; } tmp++; } // printf ("%lf\n", sum/ k); ans += sum / k; node[pos].v = sum / k; } return ans; } int main () { scanf ("%d", &T); while (T--) { scanf ("%d%d%d", &n, &m, &k); for (int i = 0; i < n; i++) { scanf ("%I64d%lf", &node[i].x, &node[i].v); node[i].id = i; } printf ("%.6lf\n", solve()); } return 0; }
HDU4995Revenge of kNN(暴力)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。