排序之后找到a[(1+n)/2]這個(gè)點(diǎn)，就是最優(yōu)點(diǎn)，然后把n個(gè)數(shù)字的差值加起來(lái)就行了。
可以這么考慮：如果n為偶數(shù)，取a[(1+n)/2]時(shí)的解為ans。如果取a[(1+n)/2]-1，那么這個(gè)數(shù)字左邊有n/2個(gè)數(shù)字，右邊有n/2個(gè)數(shù)字，不如ans更優(yōu)。奇數(shù)時(shí)類似考慮。
以下是我的代碼：
#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 閱讀(904)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
題目分類：基礎(chǔ)/模擬