快递中转点——高级

Description

在浙师大的中轴线上，分布着许多公寓，而宅男宅女们每天会产生数千，甚至上万笔快递订单。想锻炼一下经商能力的CC，想到了代理一个快递中转点，那每天一定能赚不少钱。每笔订单必须当天送达寝室。
为了简化问题，CC认为所有寝室都在一条坐标轴上，并且每个寝室都在轴上有一个坐标，每天他都会把所有快递放在一个中转点上，然后开始派送。

可是为了World Final的大业，CC每天还要花大量的时间在实验室做题，因此，现在CC想要知道，他的快递中转站开在什么位置(位置可以是轴上任意点，也可以和寝室位置重合)，能使得送完所有订单所走的路程最短。那么就请你和CC一起解决一下这个小问题吧。

Input

测试数据第一行一个整数N（1<=N<=1000）表示在轴上共有N个寝室需要送达快递。
接下来N行，每行一个整数ai（0<=ai<=1,000,000）表示每个寝室的位置。

Output

包含两个整数，分别是你确定的中转站位置，以及中转站到所有寝室的距离之和。

Sample Input

5
0
20
40
10
30

1
20
Sample Output

20 60

20 0

思路：
就是一道数学题，求解一个在数轴上，什么点到各点的距离最小。
把每个点都放在数轴上，就需要先排序。
中心的位置到各个位置之距离和最小，中心位置就是a[n/2]，如果n是偶数，把中转站放在a[n/2-1]到a[n/2]之间都是一样的，所以直接放在寝室那就好了
（一般来说中转站什么的要在中心的位置比较方便，也是这样距离上比较短）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<stdio.h>
int main()
{
int n,i,j,k,t;
long long int
sum=0;
long long int a[999],b[999];
long long int m;
while(scanf("%d",&n)!=EOF){
for(i=0;i<n;i++)
{
scanf("%lld",&a[i]);
}
for(i=0;i<n-1;i++){//排序
for(j=0;j<n-i-1;j++){
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
m=a[n/2];//中心位置
for(i=0;i<n;i++)//加距离
{
if(m-a[i]>=0)
{
sum+=(m-a[i]);
}
else
{
sum+=(a[i]-m);
}
}
printf("%lld %lldnn",m,sum);
}
return 0;
}

最后

以上就是繁荣棉花糖最近收集整理的关于快递中转点——高级的全部内容，更多相关快递中转点——高级内容请搜索靠谱客的其他文章。