问题描述
寒假时，ACBOY要去拜访许多朋友。恰巧他所有朋友的家都在平面坐标的X轴上。ACBOY可以选择任意一个朋友的家出发访问，但每次访问结束都要回到出发点。ACBOY怎么走花费时间最少？
输入
输入首先是一个正整数 M，表示 M 个测试实例。每个实例的输入有两行，首先是一个正整数 N (N <= 500)，表示有 N 个朋友，下一行是 N 个正整数，表示在X轴上的具体坐标。所有数据均小于 100000。
输出
对于每一个输入实例，输出访问完所有朋友的最小时间。回程时间不计。每个输出占一行。
样例
Input计
2
2
2 4
3
2 4 6
Output
2
4
分析
任意选取 N 点序列内部的一点。将两边的点自远到近一一对应得到线段或单个点，易知线段数量最大时的点 N 为最佳出发点。故应选取序列的中位数。
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';
}
}
