題目連結:
題目大意:
給定一正整數 T(1 ≦ T ≦ 10),代表有 T 組測試資料。每組測試資料佔兩列,第一列給定一正整數 N (1 ≦ N ≦ 1, 000, 000),代表一標準座標平面上有 N 個點;第二列給定 2N 個整數,每兩個整數 x 、 y 為一組,代表其中一點的 x 、 y 座標值。
請找出一點(xo,yo),使得此點到這 N 個點的曼哈頓距離(|xo - xi| + |yo - yi|,也就是座標值的差之絕對值和)之和為最小,輸出這個最小的距離和即可。
範例輸入:
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 )。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。