一?問題描述

有 N 家旅館，每家旅館都有位置和價格，有 M 個客人希望找到一家價格可接受的最近旅館。

10年積累的成都做網(wǎng)站、網(wǎng)站制作經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識你，你也不認(rèn)識我。但先網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有廣東免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。二?輸入和輸出 1?輸入

每個測試用例的第 1 行都包含兩個整數(shù) N（N ≤200000）和 M（M ≤20000），分別表示旅館數(shù)量和客人數(shù)量。接下來的 N 行，每行都包含3個整數(shù) x、y 和 c（1≤x , y,c ≤N），其中 x、y 是旅館的坐標(biāo)，c 是其價格，保證 N 個旅館都有不同的 x、y 和 c 。接下來的 M 行，每行都描述一個客人的查詢，其中 x 、y 是客人的坐標(biāo)，c 是客人可接受的最高價格。

2?輸出

對每個客人的查詢，都單行輸出價格可接受的最近旅館。若有多個旅館的價格可以接受且距離最小，則輸出第 1 個。

三?輸入和輸出樣例 1?輸入樣例

2

3 3

1 1 1

3 2 3

2 3 2

2 2 1

2 2 2

2 2 3

5 5

1 4 4

2 1 2

4 5 3

5 2 1

3 3 5

3 3 1

3 3 2

3 3 3

3 3 4

3 3 5

2?輸出樣例

1 1 1

2 3 2

3 2 3

5 2 1

2 1 2

2 1 2

1 4 4

3 3 5

四?分析和設(shè)計 1?分析

本問題為三維數(shù)據(jù)，包括二維坐標(biāo)和價格，可采用 KD 樹解決。

2?算法設(shè)計

（1）根據(jù)輸入數(shù)據(jù)的二維坐標(biāo)創(chuàng)建 KD 樹。

（2）在 KD 樹中查詢距離 p 最近且價格不超過 c 的旅館。

3?算法實現(xiàn)

查詢距離給定點 p 最近且價格不超過c 的點，算法步驟如下。

（1）創(chuàng)建一個序?qū)Γ?1 個元素記錄當(dāng)前節(jié)點到 p 的距離，第 2 個元素記錄當(dāng)前節(jié)點；然后定義一個變量 res，存儲離 p 最近且價格不超過 c 的序?qū)Α?/p>

（2）查詢時從樹根開始，首先計算樹根與 p 的距離，用 cur 記錄距離、節(jié)點序?qū)Α?/p>

（3）若 p.x [dim]

（4）若 lc 不空，則在 lc 中遞歸查詢 query(lc, m , dep+1, p)。

（5）若還沒有答案，且當(dāng)前節(jié)點的價格小于 p 的價格，則更新答案為當(dāng)前節(jié)點 res=cur，flag=1，還需要在右子樹中查詢；若當(dāng)前節(jié)點的價格小于 p 的價格且當(dāng)前節(jié)點到 p 的距離小于 res 到 p 的距離，或者

兩者相等但 cur 的序號在前，則更新 res=cur；若以 p 為球心且以 p 到?res 的距離為半徑的圓與樹根的另一區(qū)域相交，則 flag=1，還需要在右子樹中查詢。

（6）若 rc 不空且 flag=1，則在 rc 中遞歸查詢 query(rc,m,dep+1, p)。

五?代碼

package com.platform.modules.alg.alglib.hdu5992;

import javafx.util.Pair;

import java.util.Arrays;

public class Hdu5992 {
    private int inf = 0x3f3f3f3f;
    private int maxn = 200000 + 10;
    int idx;
    public String output = "";
    int sz[] = new int[maxn<< 2];
    Node a[] = new Node[maxn];
    Node kd[] = new Node[maxn<< 2];

    Pairres;

    public Hdu5992() {
        res = new Pair<>(-1L, new Node());

        for (int i = 0; i< a.length; i++) {
            a[i] = new Node();
        }

        for (int i = 0; i< kd.length; i++) {
            kd[i] = new Node();
        }
    }

    void build(int rt, int l, int r, int dep) {
        if (l >r) return;
        sz[rt] = 1;
        sz[rt<< 1] = sz[rt<< 1 | 1] = 0;
        idx = dep % 2;// 注意只按二維建樹
        int mid = (l + r) >>1;
        Arrays.sort(a, l, r + 1);
        kd[rt] = a[mid];
        build(rt<< 1, l, mid - 1, dep + 1);
        build(rt<< 1 | 1, mid + 1, r, dep + 1);
    }

    Long dis(int rt, Node p) { // 求距離二維
        return Long.valueOf((p.x[0] - kd[rt].x[0]) * (p.x[0] - kd[rt].x[0]) +
                (p.x[1] - kd[rt].x[1]) * (p.x[1] - kd[rt].x[1]));
    }

    void query(int rt, Node p, int dep) {
        if (sz[rt] == 0) return;
        Paircur = new Pair(dis(rt, p), kd[rt]);
        int lc = rt<< 1, rc = rt<< 1 | 1, dim = dep % 2, flag = 0;
        if (p.x[dim] >= kd[rt].x[dim]) {
            int temp = lc;
            lc = rc;
            rc = temp;
        }

        if (sz[lc] >0)
            query(lc, p, dep + 1);
        if (res.getKey() == -1) {//第一個
            if (cur.getValue().x[2]<= p.x[2])
                res = cur;
            flag = 1;
        } else {
            if (cur.getValue().x[2]<= p.x[2] && (cur.getKey()< res.getKey()
                    || (cur.getKey() == res.getKey() && cur.getValue().id< res.getValue().id)))
                res = cur;
            if ((kd[rt].x[dim] - p.x[dim]) * (kd[rt].x[dim] - p.x[dim])<= res.getKey())
                flag = 1;
        }
        if (sz[rc] >0 && flag == 1)
            query(rc, p, dep + 1);
    }

    public String cal(String input) {
        int t, n, m;
        String[] line = input.split("\n");
        t = Integer.parseInt(line[0]);
        int count = 1;
        while (t-- >0) {
            String[] num = line[count++].split(" ");
            n = Integer.parseInt(num[0]);
            m = Integer.parseInt(num[1]);
            for (int i = 0; i< n; ++i) {
                String[] postion = line[count++].split(" ");
                for (int j = 0; j< 3; ++j) {
                    a[i].x[j] = Integer.parseInt(postion[j]);
                }
                a[i].id = i;
            }
            build(1, 0, n - 1, 0);
            while (m-- >0) {
                Node p = new Node();
                Node ans;
                String[] query = line[count++].split(" ");
                for (int i = 0; i< 3; ++i) {
                    p.x[i] = Integer.parseInt(query[i]);
                }


                res = new Pair<>(-1L, new Node());
                query(1, p, 0);
                ans = res.getValue();
                output += ans.x[0] + " " + ans.x[1] + " " + ans.x[2] + "\n";
            }
        }
        return output;
    }

    class Node implements Comparable{
        int x[] = new int[3];
        int id; // 輸入序號


        public int compareTo(Node o) {
            return x[idx] >o.x[idx] ? 1 : -1; // 升序
        }
    }
}

六?測試?

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享標(biāo)題：找旅館問題-創(chuàng)新互聯(lián)
當(dāng)前網(wǎng)址：http://weahome.cn/article/espos.html