HDU4995Revenge of kNN(暴力） - c++编程基础

TOP

HDU4995Revenge of kNN(暴力）

2015-07-20 17:41:50 来源: 作者: 【大中小】浏览:4次

题目：HDU4995Revenge of kNN(暴力）

题目大意:给你一维的N个点，每个点有X坐标，和V值，然后现在给你M个修改，接下来的M行每行给你一个Qi（前面的N个点的序号1--N）。要求每次取离X（Qi）最近的K个邻居，然后将X(Qi)的值改为（这K个邻居的值的平均值），最后输出这M次修改值的和。如果距离相同的话就取原先读入下标小的那个邻居。

解题思路:先将这N个点按照X的值排序 + 暴力。Qi是下标不是X，这个没看清楚，坑死了。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
      using namespace std; const int N = 1e5 + 5; typedef long long ll; map
      
        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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 5000 Clone（鞍山网络赛D题）	下一篇：UVA12232 - Exclusive-OR（带权并..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: