AcWing 104. 貨倉選址
在一條數軸上有 N 家商店，它們的坐標分別為 A1～AN，
現在需要在數軸上建立一家貨倉，每天清晨，從貨倉到每家商店都要運送一車商品，
為了提高效率，求把貨倉建在何處，可以使得貨倉到每家商店的距離之和最小，
輸入格式
第一行輸入整數 N，
第二行 N 個整數 A1～AN，
輸出格式
輸出一個整數，表示距離之和的最小值，
資料范圍
1≤N≤100000,
0≤Ai≤40000
輸入樣例：
4
6 2 9 1
輸出樣例：
12
對于這樣一條數軸，怎樣選點，才能保證那個點到每個點的距離和是最小的？設這個點的位置為x，則距離就是
∣
x
?
1
∣
+
∣
x
?
2
∣
+
∣
x
?
6
∣
+
∣
x
?
9
∣
|x-1|+|x-2|+|x-6|+|x-9|
∣x?1∣+∣x?2∣+∣x?6∣+∣x?9∣對于這個這個帶絕對值的函式，求出最小值也不是什么難事，只要讓2<=x<=6就可以，最小值為12，且是定值，在其他范圍，你求出的距離都會多加一些長度，例如你令x=1.5，那么x到1和2的距離和是1，再加上到6和9的距離和就是13，多出來的這個距離“1”，就是因為多算了2次“0.5”，這兩次0.5就是6到1.5和9到1.5產生的，
所以經過上面的解釋，這個x只要放在最中間2個數（偶數情況）的范圍之間，總和就是最小的，
那奇數情況呢？沒有最中間的兩個數，
就像這個數軸，沒有最中間的2個數，但是有最中間的數，那就是“5”，剛才說過沒有這個“5“的情況，5這個數在[2,6]之間，所以干脆直接讓x=5再求距離，就是在上面的情況下，再加上x到5的距離“0”，
所以奇數的情況就是找最中間的數,把那個數定為x，再算剩下的點到x的距離，
本質上講，就是絕對值函式求最小值，
上面我寫的解釋可能比較繁瑣，如果有更好的想法或者已經理解，可以忽略，（這個解釋是為了我復習用的 ）
下面附上代碼
#include<bits/stdc++.h>
using namespace std;
int a[100001];
bool cmp(int i,int j)
{
return i<j;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n,cmp); //相當于在數軸上，把數排好順序
int res=0;
for(int i=0;i<n/2;i++) //兩個點的距離，就是那個大的數減去小的數
{
res=res+a[n-1-i]-a[i]; //這就是2個在順序上對稱的點的距離
}
printf("%d\n",res);
return 0;
}
如果你有任何建議或者批評和補充，請留言指出，不勝感激，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/267414.html
標籤：其他
下一篇：演算法之快速冪運算的實作方法