HDU5992-Finding Hotels(KD-Tree)

题目链接:HDU5992-Finding Hotels

题意:

二维坐标上有n个旅馆,每个旅馆都有有个价格,有m个人,给出每个人所在的坐标和所能支付的最大价格,问距离每个人最近的可负担的旅馆的位置。

题解:

KD-Tree模板。

把旅馆的二维坐标+费用+编号共4维放入KD-T。

然后进行查询即可。

参考代码:

#include <bits/stdc++.h>
#define IL inline
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;

int n, m, T;
int idx, flag[MAXN << 2];

struct kd_node
{
    int f[5];
    int id;
    bool operator<(const kd_node &rhs) const
    {
        return f[idx] < rhs.f[idx];
    }
} a[MAXN];
pair<ll, kd_node> ans;
struct kdtree
{
    int k;
    bool vis[MAXN << 2];
    kd_node dat[MAXN << 2];
    void build(int l, int r, int rt, int dep)
    {
        if (l > r)
            return;
        vis[rt] = 1;
        vis[rt << 1] = vis[rt << 1 | 1] = 0;
        idx = dep % k;
        int m = (l + r) >> 1;
        nth_element(a + l, a + m, a + r + 1);
        dat[rt] = a[m];
        build(l, m - 1, rt << 1, dep + 1);
        build(m + 1, r, rt << 1 | 1, dep + 1);
    }
    void query(kd_node p, int rt, int dep)
    {
        if (!vis[rt])
            return;
        pair<ll, kd_node> cur(0, dat[rt]);
        for (int i = 0; i < k; i++)
            cur.first += 1ll * (cur.second.f[i] - p.f[i]) * (cur.second.f[i] - p.f[i]);
        int dim = dep % k;
        bool fg = 0;
        int x = rt << 1, y = rt << 1 | 1;
        if (p.f[dim] >= dat[rt].f[dim])
            swap(x, y);
        if (vis[x])
            query(p, x, dep + 1);
        if (ans.first == -1)
        {
            if (dat[rt].f[2] <= p.f[2])
                ans = cur;
            fg = 1;
        }
        else
        {
            if (cur.first < ans.first && dat[rt].f[2] <= p.f[2])
                ans = cur;
            else if (cur.first == ans.first && dat[rt].f[2] <= p.f[2] && dat[rt].f[3] < ans.second.f[3])
                ans = cur;
            if (1ll * (p.f[dim] - dat[rt].f[dim]) * (p.f[dim] - dat[rt].f[dim]) < ans.first)
                fg = 1;
        }
        if (vis[y] && fg)
            query(p, y, dep + 1);
    }
} kd;
int main()
{
    scanf("%d", &T);
    kd.k = 2;
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= 2; j++)
                scanf("%d", &a[i].f[j]);
            a[i].f[3] = i;
        }
        kd.build(1, n, 1, 0);
        while (m--)
        {
            kd_node q;
            for (int i = 0; i <= 2; i++)
                scanf("%d", &q.f[i]), ans.second.f[i] = 0;
            ans.first = -1;
            kd.query(q, 1, 0);
            for (int i = 0; i <= 1; i++)
                printf("%d ", ans.second.f[i]);
            printf("%d\n", ans.second.f[2]);
        }
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。