首页 > 代码库 > hdu 2083
hdu 2083
原题连接:
http://acm.hdu.edu.cn/showproblem.php?pid=2083
题意:
给定x轴上n个点,求任意一点到其他点距离和的最小值。
思路:
(1)当n=2时:sum=|a-b|(点用a,b,c.......表示);
(2)当n>2时:以n=3为例,a=1,b=5,c=10。sum1=|a-b|+|a-c|=13、sum2=|b-a|+|b-c|=6、sum3=|c-a|+|c-b|=14 (数据可自己模拟测试);
由此可以看出当点是有序排列时,中间的点到其他点的距离和是最小的(n为奇、偶时,需另判断);
代码:
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
int t,n,a[501];
int i;
cin>>t;
while(t--)
{
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
if(n%2==0)
{
long long A=0,B=0;
for(i=0;i<n;i++)
{
A+=abs(a[n/2]-a[i]);
B+=abs(a[n/2-1]-a[i]);
}
if(A>B)
printf("%lld\n",B);
else
printf("%lld\n",A);
}
else
{
long long A=0;
for(i=0;i<n;i++)
{
A+=abs(a[n/2]-a[i]);
}
printf("%lld\n",A);
}
}
return 0;
}
hdu 2083