932
街道最短路徑
街區最短路徑問題時間限製：3000 ms | 內存限製：65535 KB
難度：4
描述
一個街區有很多住戶，街區的街道隻能為東西、南北兩種方向。
住戶隻可以沿著街道行走。
各個街道之間的間隔相等。
用(x,y)來表示住戶坐在的街區。
例如（4,20），表示用戶在東西方向第4個街道，南北方向第20個街道。
現在要建一個郵局，使得各個住戶到郵局的距離之和最少。
求現在這個郵局應該建在那個地方使得所有住戶距離之和最小；
輸入
第一行一個整數n<20，表示有n組測試數據，下麵是n組數據;
每組第一行一個整數m<20,表示本組有m個住戶，下麵的m行每行有兩個整數0<x,y<100，表示某個用戶所在街區的坐標。
m行後是新一組的數據；
輸出
每組數據輸出到郵局最小的距離和，回車結束；
樣例輸入
2
3
1 1
2 1
1 2
5
2 9
5 20
11 9
1 1
1 20
樣例輸出
2
44
解題的關鍵就在於排序求出中間的經x和y。
然後累加求和就行！
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
int n;
int x[20], y[20];
cin >> n;
for (int test = 1; test <= n; test++)
{
int m;
cin >> m;
for (int i = 0; i < m; i++)
cin >> x[i] >> y[i];
//從小到大排序
sort(x, x+m);
sort(y, y+m);
int minSum = 0;
for (int i = 0; i < m; i++)
{
minSum += abs(x[i] - x[m/2]);
minSum += abs(y[i] - y[m/2]);
}
cout << minSum << endl;
}
return 0;
}
最後更新：2017-04-02 15:14:50