心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
排序之后找到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)  编辑 收藏 引用 所属分类: 题目分类:基础/模拟

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理