2009-10-02 22:33:12來源不明

板橋高中98資訊能力競賽 直線最小距離和

作法 : 排序

排序好,把中位數取出來,之後把所有距離加總即可

你也可以試著窮舉所有點.

/*************************************************************/

#include <stdlib.h>
#include <stdio.h>
int partition(int [],int ,int);
void quicksort(int [], int ,int);
main()
{
   int t,n,a,b,c;
   scanf("%d",&t);
   while(t--)
      {
          scanf("%d",&n);
          int num[1001]={0};
          for(a=0;a<n;a++)
             scanf("%d",&num[a]);
          quicksort(num,0,n-1);
          int ss=(num[n/2]+num[(n-1)/2])/2,sum=0;
          for(a=0;a<n;a++)
             sum+=abs(ss-num[a]);
          printf("%d\n",sum);
      }
   return 0;
}
int partition (int num[],int left ,int right)
{
   int a=left-1,b,s=num[right],temp;
   for(b=left;b<right;b++)
       if(num[b]>=s)
          {
             a++;
             temp=num[a];
             num[a]=num[b];
             num[b]=temp;
          }
       temp=num[a+1];
       num[a+1]=num[right];
       num[right]=temp;
    return a+1;
}
void quicksort (int num[],int left,int right)
{
   int q;
   if(left<right)
      {
        q=partition(num,left,right);
        quicksort(num,left,q-1);
        quicksort(num,q+1,right);
      }
}