AcWing 104. 货仓选址
原题链接
简单
作者:
hii
,
2021-01-09 10:37:43
,
所有人可见
,
阅读 330
/*
**贪心+绝对值不等式**
设我们排序后,这些点在的坐标为 x1, x2, x3, x4...., xn
设选定的点的坐标为 x
那么所求结果f(x) = |x1 - x| + |x2 - x| + |x3 - x| + ...|xn - x|
= (|x1 -x| + |xn - x|) + (|x2 - x| + |xn-1 - x|) + ...
我们求其中的一项: (|x1 -x| + |xn - x|), 就是在x轴上选一点,使得这个点到 x1 和 xn 两点的距离之和最小
我们发现:只要这两个点选在[x1, xn]内,这一项的值总等于|xn - x1|,
选在其他位置,必然大于 |xn - x1|
------|-----------------|-------
x1 xn
综上
f(x) >= xn - x1 + xn-1 - x2 + ....
那么,我们能不能取到 = 呢?答案是 x 取 n / 2 位置的数时,x 就在上面所有的区间内,此时取到 =
证明:
**注意我们的下标是从 0 开始的**
如果数的总个数 n 为偶数:
那么 n/2 的位置的数就是区间长度最小的区间[Xn/2-1, Xn/2] 的右端点,满足条件
如果数的总个数 n 为奇数:
那么 n/2 的位置的数就是区间长度最小的区间[Xn/2, Xn/2]内,满足条件
*/
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
// 顺便练一下快排
void qsort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
while (q[++i] < x);
while (q[--j] > x);
if (i < j) swap(q[i], q[j]);
}
qsort(q, l, j);
qsort(q, j + 1, r);
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++) cin >> a[i];
qsort(a, 0, n - 1);
int mid = a[n / 2];
int res = 0;
for (int i = 0; i < n; i ++) res += abs(a[i] - mid);
cout << res << endl;
return 0;
}