货仓选址
n个商店一条线,找一个点使其到n个商店的距离最小,求出最小距离和
思路:n为奇数,则点为中间点;n为偶数,点为中间两个点的中间。即点为n个点的中位数点
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100000;
int a[N]; //点的坐标
int n;
int main()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
int res;
for(int i = 0; i <n; i++)
{
res += abs(a[i] - a[n/2]); //各点与中位数点的距离之和
}
cout << res;
return 0;
}