首页 > 代码库 > BestCoder9 1003 Revenge of kNN(hdu 4995) 解题报告

BestCoder9 1003 Revenge of kNN(hdu 4995) 解题报告

2024-07-24 01:36:53   219人阅读

题目链接：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 }
View Code

 

BestCoder9 1003 Revenge of kNN(hdu 4995) 解题报告


联系
我们