f438 - 855 - Lunch in Grid City
題目描述
題目要求在一個網格城市中找到一個地點，使得所有朋友到該地點的曼哈頓距離總和最小。如果有多個地點滿足條件，則選擇街號和大道號都最小的地點。
解題思路
由於曼哈頓距離的特性，最佳地點一定是所有朋友街號的中位數和大道號的中位數的交點。因此，我們只需要分別對街號和大道號進行排序，然後找到中位數即可。由於題目要求在有多個解的情況下選擇街號和大道號都最小的解，因此直接取排序後的數組中間元素即可。如果朋友數量為偶數，則取 (f-1)/2 作為中位數索引。
複雜度分析
- 時間複雜度: O(f log f)，其中 f 是朋友的數量。主要時間花費在排序街號和大道號上。
- 空間複雜度: O(f)，用於存儲街號和大道號的數組。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int t,s,a,f;
cin >> t;
while(t--){
cin >> s >> a >> f;
int x[f],y[f];
for(int i=0;i<f;++i){
cin >> x[i] >> y[i];
}
sort(x,x+f);
sort(y,y+f);
cout << "(Street: " << x[(f-1)/2] << ", Avenue: " << y[(f-1)/2] << ")\n";
}
}