快递中转点

参考blog：https://blog.csdn.net/cjj122/article/details/75579390

在笔直的余姚大街上，分布着密密麻麻的店铺，每天有成千上万笔快递订单。小明想开个快递中转站，那每天一定
能赚不少钱。每笔订单必须当天送达指定店铺。为了简化问题，小明认为所有店铺都在一条坐标轴上，并且每个店
铺都在轴上有一个坐标，每天他都会把所有快递放在一个中转点上，然后一件一件开始派送。可是小明是个懒人，
他想尽可能少走路。他的快递中转站开在什么位置(位置可以是轴上任意点，也可以和店铺位置重合)，能使得中转
站到所有店铺的距离之和的最小。那么就请你和小明一起解决一下这个小问题吧，找到这个最小值。

Input

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

Output

包含一个整数，中转站到所有店铺的距离之和的最小值。

Sample Input

Sample Output

60
//快递中转站建立在20的位置，则到5个点的距离分别是0，20，40，10，30

sol:先将店铺的位置按坐标轴从小到大排序，得0，10，20，30，40，调整法：假设快递中转站设在第一个点与第二个点比较，设在第一个点，第一个点不走，后面四个点都要多走10；设在第二个点，第一个点多走10，后面三个点少走10，显然比前面优。但多走的点还是比少走的少，所以再向右调整，选第三个点。与选第二个点比较，左边两个点多走10，右边两个点少走10。这就是中位数原理，假设n为奇数，选在n/2+1的位置，如果是偶数，选在n/2和n/2+1的位置都一样。本题跟各个点之间的距离没有关系，只跟有多少个点相关。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     long long n,f[1101],c,ans=0;
 6     cin>>n;
 7     for(int i=1;i<=n;i++)
 8         cin>>f[i];
 9     sort(f+1,f+1+n);
10     c=f[(n+1)/2];
11     for(int i=1;i<=n;i++)
12              ans=ans+abs(f[i]-c);
13      
14     cout<<ans;
15     return 0;
16 }

原文链接: https://www.cnblogs.com/cutepota/p/12125421.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/308870

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

快递中转点

Input

Output

Sample Input

Sample Output

相关推荐