树和二叉树_13

---

一、HZOJ-245

货仓选址
​
在一条数轴上有 N 家商店，他们的坐标分别为 A[1]−A[N]。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小，输出最短距离之和。

样例输入：
第一行输入一个数 N。（1≤N≤100000）
​ 接下来一行，输入 N 个数，表示商店的坐标。

5
1 3 5 6 10

样例输出： 输出最短距离之和。

12

---

二、题解

1.引库

 #include <iostream>#include <cstdio>#include <cstdlib>#include <queue>#include <stack>#include <algorithm>#include <string>#include <map>#include <set>#include <vector>using namespace std;

2.代码

int main(){int n;cin>>n;vector<int> arr;for(int i=0,a;i<n;i++){cin>>a;arr.push_back(a);}sort(arr.begin(),arr.end());int ans=0;for(int i=0;i<n/2;i++){ans+=(arr[n-1-i]-arr[i]);}cout<<ans<<endl;return 0;
}

**思考：**进阶的题
定义三元组(a,b,c)(其中a,b,c均为正数)的距离D=a-b|+|b-c|+|c-a|。给定3个非空整数集合S1、S2和S3，按升序分别存储在3个数组中。设计一个尽可能高效的算法,计算并输出所有可能的三元组(a,b,c)(abc分别在三个集合)中的最小距离。
S1 ={-1,0,9},S2 ={-25,-10,10,11},S3= {2,9,17,30,41} ,则最小距离为⒉,相应的三元组为(9,10,9)
解法：贪心+三指针后移
假设三个数组出来三个数从小到大abc
可以尝试c和b不管怎么后移距离只会变大和不变，只有最小值a向右移才会变小，所以只需要遍历数组直到最小的值右移不动结束即可。