b063 - 2. 衛星通訊中心
題目描述
題目要求找到一個點，使得這個點到所有給定城市（座標）的曼哈頓距離總和最小。如果有多個點可以達到最小距離，則輸出 x 座標最小的點，如果 x 座標相同，則輸出 y 座標最小的點。
解題思路
此題採用暴力解法。遍歷每個城市，將其視為衛星通訊中心的位置，計算該位置到所有其他城市的曼哈頓距離總和。記錄最小的總距離以及對應的城市座標。最後輸出座標和最小距離。曼哈頓距離的計算方式為 abs(x1 - x2) + abs(y1 - y2)。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是城市的數量。外層迴圈遍歷每個城市作為通訊中心，內層迴圈計算到其他所有城市的距離。
- 空間複雜度: O(n)，用於儲存城市座標。
程式碼
#include <iostream>
using namespace std;
int main(){
int n;
while(cin >> n){
int a[n][3],min=10000001,mx,my;
for(int i=0;i<n;i++){
cin >> a[i][0] >> a[i][1];
a[i][2]=0;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
a[i][2]+=abs(a[i][0]-a[j][0])+abs(a[i][1]-a[j][1]);
}
if(min>a[i][2]){
min=a[i][2];
mx=a[i][0];
my=a[i][1];
}
else if(min==a[i][2]&&a[i][0]<mx){
mx=a[i][0];
my=a[i][1];
}
else if(min==a[i][2]&&a[i][0]==mx&&a[i][1]<my){
mx=a[i][0];
my=a[i][1];
}
}
cout << mx << " " << my << "\n" << min << "\n";
}
}