1. 题目

传送门= ̄ω ̄=

题意:
首先给出 $n$个点,然后询问 $m$个坐标,对于每个坐标要求输出前面给出的 $n$个点中距离该坐标最近的 $k$个点是那些。

数据范围为 $50000$

2. 题解

具体做法参考这个题解:传送门= ̄ω ̄=

只不过是把曼哈顿距离改成了欧几里得距离,做法依然相同,甚至没有了插入操作。

至于要求输出前 $k$个最近点,搞个优先队列,队首元素距离最远,就方便剪枝,也方便删除无用答案。

代码:

#pragma GCC optimize("Ofast,no-stack-protector")

#include <bits/stdc++.h>

#define NS (50005)
#define MKP make_pair

using namespace std;

typedef pair<int,int> PII;

template <typename _Tp>inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int squ(int a){return a * a;}

int n, ds, D, root, sz, m, k;

priority_queue<PII> pq;

stack<PII> ans;

struct N
{
    int d[5], mx[5], mn[5], l, r;
    int& operator [] (int a){return d[a];}
    bool operator < (N another) const {return d[D] < another[D];}
    void print()
    {
        for (int i = 0; i < ds - 1; i += 1) printf("%d ", d[i]);
        printf("%d\n", d[ds-1]);
    }
}arr[NS], e[NS], q;

void pup(int a)
{
    N& l = e[e[a].l], & r = e[e[a].r];
    for (int i = 0; i < ds; i += 1)
    {
        e[a].mx[i] = e[a].mn[i] = e[a][i];
        if (e[a].l)
        {
            e[a].mx[i] = max(e[a].mx[i], l.mx[i]);
            e[a].mn[i] = min(e[a].mn[i], l.mn[i]);
        }
        if (e[a].r)
        {
            e[a].mx[i] = max(e[a].mx[i], r.mx[i]);
            e[a].mn[i] = min(e[a].mn[i], r.mn[i]);
        }
    }
}

int dis(N p, int a)
{
    int tot = 0;
    for (int i = 0; i < ds; i += 1) tot += squ(p[i] - e[a][i]);
    return tot;
}

int get_dis(N p, int a)
{
    int tot = 0;
    for (int i = 0; i < ds; i += 1)
        tot += squ(max(e[a].mn[i] - p[i], 0)) + squ(max(p[i] - e[a].mx[i], 0));
    return tot;
}

void query(int a = root)
{
    if (!a) return;
    PII nxt = MKP(dis(q, a), a);
    if (pq.size() < k) pq.push(nxt);
    else if (nxt < pq.top()) pq.pop(), pq.push(nxt);
    int dl = INT_MAX, dr = INT_MAX;
    if (e[a].l) dl = get_dis(q, e[a].l);
    if (e[a].r) dr = get_dis(q, e[a].r);
    if (dl < dr)
    {
        if (dl < pq.top().first || pq.size() < k) query(e[a].l);
        if (dr < pq.top().first || pq.size() < k) query(e[a].r);
    }
    else
    {
        if (dr < pq.top().first || pq.size() < k) query(e[a].r);
        if (dl < pq.top().first || pq.size() < k) query(e[a].l);
    }
}

int Build(int l, int r, int d = 0)
{
    if (l > r) return 0;
    D = d;
    int a = ++sz, mid = (l + r) >> 1;
    nth_element(arr + l, arr + mid, arr + r + 1);
    e[a] = arr[mid];
    e[a].l = Build(l, mid - 1, (d + 1) % ds);
    e[a].r = Build(mid + 1, r, (d + 1) % ds);
    pup(a); return a;
}

int main (int argc, char const* argv[])
{
    while (sz = 0, ~scanf("%d%d", & n, & ds))
    {
        for (int i = 1; i <= n; i += 1)
            for (int j = 0; j < ds; j += 1)
                IN(arr[i][j]);
        root = Build(1, n), IN(m);
        while (m--)
        {
            for (int i = 0; i < ds; i += 1) IN(q[i]);
            IN(k), query();
            printf("the closest %d points are:\n", k);
            while (!pq.empty()) ans.push(pq.top()), pq.pop();
            while (!ans.empty()) e[ans.top().second].print(), ans.pop();
        }
    }
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

2 条评论

Rayment · 2018年6月10日 8:58 上午

当优先队列元素少于要求个数但子节点为空时应该是不能进入子节点的。比如缩这组数据,输出的三个点应该分别是 (1,1),(1,3) 和 (3,4)

3 2
1 1
1 3
3 4
1
3 0
3

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注