寒假的时候,ACBOY要去拜访很多朋友,恰巧他所有朋友的家都处在坐标平面的X轴上.ACBOY可以任意选择一个朋友的家开始访问,但是每次访问后他都必须回到出发点,然后才能去访问下一个朋友.比
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/25 19:16:39
![寒假的时候,ACBOY要去拜访很多朋友,恰巧他所有朋友的家都处在坐标平面的X轴上.ACBOY可以任意选择一个朋友的家开始访问,但是每次访问后他都必须回到出发点,然后才能去访问下一个朋友.比](/uploads/image/z/12635457-33-7.jpg?t=%E5%AF%92%E5%81%87%E7%9A%84%E6%97%B6%E5%80%99%2CACBOY%E8%A6%81%E5%8E%BB%E6%8B%9C%E8%AE%BF%E5%BE%88%E5%A4%9A%E6%9C%8B%E5%8F%8B%2C%E6%81%B0%E5%B7%A7%E4%BB%96%E6%89%80%E6%9C%89%E6%9C%8B%E5%8F%8B%E7%9A%84%E5%AE%B6%E9%83%BD%E5%A4%84%E5%9C%A8%E5%9D%90%E6%A0%87%E5%B9%B3%E9%9D%A2%E7%9A%84X%E8%BD%B4%E4%B8%8A.ACBOY%E5%8F%AF%E4%BB%A5%E4%BB%BB%E6%84%8F%E9%80%89%E6%8B%A9%E4%B8%80%E4%B8%AA%E6%9C%8B%E5%8F%8B%E7%9A%84%E5%AE%B6%E5%BC%80%E5%A7%8B%E8%AE%BF%E9%97%AE%2C%E4%BD%86%E6%98%AF%E6%AF%8F%E6%AC%A1%E8%AE%BF%E9%97%AE%E5%90%8E%E4%BB%96%E9%83%BD%E5%BF%85%E9%A1%BB%E5%9B%9E%E5%88%B0%E5%87%BA%E5%8F%91%E7%82%B9%2C%E7%84%B6%E5%90%8E%E6%89%8D%E8%83%BD%E5%8E%BB%E8%AE%BF%E9%97%AE%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9C%8B%E5%8F%8B.%E6%AF%94)
寒假的时候,ACBOY要去拜访很多朋友,恰巧他所有朋友的家都处在坐标平面的X轴上.ACBOY可以任意选择一个朋友的家开始访问,但是每次访问后他都必须回到出发点,然后才能去访问下一个朋友.比
寒假的时候,ACBOY要去拜访很多朋友,恰巧他所有朋友的家都处在坐标平面的X轴上.ACBOY可以任意选择一个朋友的家开始访问,但是每次访问后他都必须回到出发点,然后才能去访问下一个朋友.
比如有4个朋友,对应的X轴坐标分别为1,2,3,4.当ACBOY选择坐标为2的点做为出发点时,则他最终需要的时间为 |1-2|+|2-2|+|3-2|+|4-2| = 4.
现在给出N个朋友的坐标,那么ACBOY应该怎么走才会花费时间最少呢?
Input
输入首先是一个正整数M,表示M个测试实例.每个实例的输入有2行,首先是一个正整数N(N
寒假的时候,ACBOY要去拜访很多朋友,恰巧他所有朋友的家都处在坐标平面的X轴上.ACBOY可以任意选择一个朋友的家开始访问,但是每次访问后他都必须回到出发点,然后才能去访问下一个朋友.比
#include
#include
#include
using namespace std;
int main()
{
int m;
cin >> m;
while (m--)
{
int n;
cin >> n;
int* p = new int[n];
int i;
for (i = 0; i < n; ++i)
{
cin >> p[i];
}
sort(p, p+n);
int sum = 0;
int t = n%2? n/2:n/2-1;
for (i = 0; i < n; ++i)
{
sum += abs(p[i] - p[t]);
}
cout