問題描述
寒假時丛晌，ACBOY要去拜訪許多朋友签餐。恰巧他所有朋友的家都在平面坐標的X軸上。ACBOY可以選擇任意一個朋友的家出發(fā)訪問愚战，但每次訪問結(jié)束都要回到出發(fā)點娇唯。ACBOY怎么走花費時間最少齐遵？
輸入
輸入首先是一個正整數(shù) M，表示 M 個測試實例塔插。每個實例的輸入有兩行梗摇，首先是一個正整數(shù) N (N <= 500)，表示有 N 個朋友想许，下一行是 N 個正整數(shù)伶授，表示在X軸上的具體坐標。所有數(shù)據(jù)均小于 100000流纹。
輸出
對于每一個輸入實例糜烹，輸出訪問完所有朋友的最小時間∈回程時間不計疮蹦。每個輸出占一行。
樣例
Input計
2
2
2 4
3
2 4 6
Output
2
4
分析
任意選取 N 點序列內(nèi)部的一點茸炒。將兩邊的點自遠到近一一對應(yīng)得到線段或單個點愕乎，易知線段數(shù)量最大時的點 N 為最佳出發(fā)點。故應(yīng)選取序列的中位數(shù)壁公。
AC代碼
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
int T; cin >> T; while (T--) {
int N; cin >> N;
vector<int> v;
while (N--) {
int tmp; cin >> tmp;
v.push_back(tmp);
}
sort(v.begin(), v.end());
int mid{*(v.begin() + (v.end() - v.begin()) / 2)};
int sum{0}; for (int n : v) sum += abs(n - mid);
cout << sum << '\n';
}
}
