k184. pA. 房屋推薦 (house)
Tags : 排序
Accepted rate : 69人/83人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-03-22 00:04

Content

題目敘述 : https://drive.google.com/file/d/1nDZNGCptQGcAZDxqRGcNt_wpz31clODZ/view?usp=sharing

房屋仲介小潮負責高談市的租房業務。小潮手上有編號為 $1, 2, · · · , n$ 的 $n$ 間待租的房屋,房屋 $i$ 的位置可以用二維座標 $(a_i, b_i)$ 表示,並且此房屋的月租金為 $r_i$ 元。

高談市有 $m$ 座捷運站,捷運站的編號為 $1, 2, · · · , m$,捷運站 $j$ 的位置在二維平面以座標 $(c_j , d_j )$ 表示。定義房屋 $i$ 與捷運站 $j$ 的距離為 $\sqrt{(a_i - c_j)^2 + (b_i - d_j)^2}$ 單位。

小潮發現租客的喜好如下:

1.    房屋與最近的捷運站的距離越短越好。
2.    如果兩間房屋和彼此最近的捷運站距離一樣近,月租金越小的房屋越好。
3.    如果兩間房屋和彼此最近的捷運站距離一樣近,而且月租金相同,房屋編號越小的越好。

請幫忙小潮開發一個房屋推薦系統,對房屋們進行排序,使得越是得到租客喜愛的房屋排在越前面。


如下圖為一 $n = 3$ 且 $m = 3$ 的例子,其中正方形的點 $H_1, H_2, H_3$ 分別代表房屋 $1, 2, 3$,圓點 $S_1, S_2, S_3$ 則分別代表捷運站 $1, 2, 3$ 的位置。並且:

•    第 $1$ 間房屋位在 $(2, 0)$,月租金為 $11000$ 元。
•    第 $2$ 間房屋位在 $(5, 0)$,月租金為 $12000$ 元。
•    第 $3$ 間房屋位在 $(3, 3)$,月租金為 $10000$ 元。
•    第 $1$ 座捷運站位在 $(1, 3)$。
•    第 $2$ 座捷運站位在 $(3, 0)$。
•    第 $3$ 座捷運站位在 $(5, 3)$。

測資限制

•    $1 ≤ n ≤ 10^5$。
•    $1 ≤ m ≤ 10^3$。
•    $−10^9 ≤ a_i, b_i, c_i, d_i ≤ 10^9$。
•    $0 ≤ r_i ≤ 10^9$
•    上述變數皆為整數。
•    任意一個座標最多只有一間房屋或一座捷運站,且不會有房屋和捷運站在同一座標。

Input
$n$ $m$
$a_1$ $b_1$ $r_1$
$a_2$ $b_2$ $r_2$
...
$a_n$ $b_n$ $r_n$
$c_1$ $d_1$
$c_2$ $d_2$
...
$c_m$ $d_m$

•    $n, m$ 分別代表房屋與捷運站的數量。
•    房屋 $i$ 的座標在 $(a_i, b_i)$,且租金為 $r_i$。
•    捷運站 $j$ 的座標為 $(c_j , d_j )$。

Output
$p_1$
$p_2$
...
$p_n$

•    $p_i$ 為一整數,代表排名第 $i$ 名的房屋編號。

Sample Input #1
3 3
2 0 11000
5 0 12000
3 3 10000
1 3
3 0
5 3
Sample Output #1
1
3
2
Sample Input #2
4 2
2 -2 10000
-2 1 12000
1 -3 12000
4 5 19000
1 5
4 1
Sample Output #2
4
1
2
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (1%): 1.0s , <1K
公開 測資點#1 (1%): 1.0s , <1K
公開 測資點#2 (3%): 1.0s , <1M
公開 測資點#3 (3%): 1.0s , <1M
公開 測資點#4 (3%): 1.0s , <1M
公開 測資點#5 (3%): 1.0s , <1M
公開 測資點#6 (3%): 1.0s , <1M
公開 測資點#7 (3%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
公開 測資點#10 (10%): 1.0s , <1M
公開 測資點#11 (16%): 1.0s , <10M
公開 測資點#12 (17%): 1.0s , <10M
公開 測資點#13 (17%): 1.0s , <10M
Hint :

題目和測資來源 : twpca

注意因為礙於系統問題測試資料沒辦法完整的放上來(其實這題有全放啦)。

 

子任務 分數 額外輸入限制測資點
120$n ≤ 2$#02~#07
230$n ≤ 100$#08~#10
350無額外限制#11~#13

 

如果題目有問題歡迎來信詢問!

Tags:
排序
出處:
TOI入營考2023 [管理者: Ststone1687 (Ststone) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
39495 P2006950413 (說不得) k184
11%的問題
63 2024-02-28 17:38