1087 - 仓库的位置
小明最近做起了物流生意，为了提高送货效率，小明想请你帮他确定一下仓库的最佳位置。
为了简化问题，小明认为所有的客户住所都在一条坐标轴上，并且每个住所都在轴上有一个坐标。小明每天都会将货物从仓库送到各个客户手中。
请问仓库安置在什么位置（位置可以是轴上的任意点，也可以和客户住所位置重合），能使得仓库到各个客户住所的距离之和最小？
题目输入
输入的第一行是一个整数T，表示有T组测试数据。
每组测试数据第一行是一个整数N（1<=N<=1000）表示在轴上共有N个客户住所需要送达快递。
接下来N行，每行一个整数ai（0<=ai<=30000）表示每个客户住所的位置，所有客户住所的位置均不相同。
题目输出
对于每组输入，输出一行，包含两个整数，分别是你确定的仓库位置，以及仓库到所有客户住所的距离之和。
输入/输出样例
题目输入
2 5 0 20 40 10 30 1 20
题目输出
20 60 20 0
C语言解答
#include<stdio.h> #include<math.h> int main() { int t,a[1000]; scanf("%d",&t); while(t--) { int i,j,n,b[1000],c[1000],tmp; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n;i++) { int s=0; for(j=0;j<n;j++) { s+=abs(a[i]-a[j]); } b[i]=s; c[i]=b[i]; } for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { if(b[i]>b[j]) { tmp=b[i]; b[i]=b[j]; b[j]=tmp; } } } for(i=0;i<n;i++) { if(c[i]==b[0]) { printf("%d ",a[i]); break; } } printf("%d\n",b[0]); } return 0; }
C++解答
#include<stdio.h> #include<algorithm> using namespace std; int main() { int t,n,i,a[1000],s; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); for(s=i=0;i<n/2;i++) s+=a[n-1-i]-a[i]; printf("%d %d\n",a[n/2],s); } return 0; }