切換
舊版
前往
大廳
主題

ZeroJudge - b582: 一個窩 解題心得

Not In My Back Yard | 2019-04-26 22:19:25 | 巴幣 0 | 人氣 435

題目連結:


題目大意:
給定一正整數 T(1 ≦ T ≦ 10),代表有 T 組測試資料。每組測試資料佔兩列,第一列給定一正整數 N (1 ≦ N ≦ 1, 000, 000),代表一標準座標平面上有 N 個點;第二列給定 2N 個整數,每兩個整數 x 、 y 為一組,代表其中一點的 x 、 y 座標值。

請找出一點(x,y),使得此點到這 N 個點的曼哈頓距離(|x - x| + |y - y|,也就是座標值的差之絕對值和)之和為最小,輸出這個最小的距離和即可。



範例輸入:
2
1
0 0
4
1 0 0 1 -1 0 0 -1


範例輸出:
0
4


解題思維:
這題類似,只是它要找兩個維度(分別是 x 、 y 座標)各自的中位數,並算出與其他點的曼哈頓距離即可。

而這題測試資料量非常地大。但是 cin、cout 的最佳化在此題不會比標準輸出入的 scanf、printf 函式快(甚至慢上些許)。本人不確定其中的緣由。不過有查到 cin 因為輸入型態檢查、最佳化等因素,可能導致在某些情況會比 scanf 慢。

話雖如此,cout 基本上效率是贏過 printf 的。因此網路上有人建議:輸入用 scanf 、輸出用 cout 。但是本人認為最好的還是自己根據情況多試幾次,甚至自己去寫串流(自己硬 A )。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作