排序之后找到a[(1+n)/2]这个点，就是最优点，然后把n个数字的差值加起来就行了。
可以这么考虑：如果n为偶数，取a[(1+n)/2]时的解为ans。如果取a[(1+n)/2]-1，那么这个数字左边有n/2个数字，右边有n/2个数字，不如ans更优。奇数时类似考虑。
以下是我的代码：
#include<stdio.h>
void Qsort(long *a,long begin,long end)
{
long i=begin,j=end,mid=a[(begin+end)/2],t;
do{
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j)
{
t=a[i];a[i]=a[j];a[j]=t;
i++;j--;
}
}while(i<=j);
if(begin<j) Qsort(a,begin,j);
if(i<end) Qsort(a,i,end);
}
long Abs(long x)
{
return (x>0?x:-x);
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
const long maxn=507;
long test;
scanf("%ld",&test);
while(test--)
{
long n,mid,ans,a[maxn];
scanf("%ld",&n);
for(long i=1;i<=n;i++) scanf("%ld",&a[i]);
Qsort(a,1,n);
mid=a[(1+n)/2];
ans=0;
for(long i=1;i<=n;i++)
ans+=Abs(mid-a[i]);
printf("%ld\n",ans);
}
return 0;
}
posted on 2010-01-22 13:05
lee1r 阅读(899)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：基础/模拟