货仓选址
用数学公式表达题意,假设有位置a1~an,假设选址在x位置处,则有:
如何让这个最小,我们把两个式子整合一下,利用绝对值不等式:
我们知道:
如下图所示:到A,B两点,利用反证法可知:只有在A,B之间的点到A,B距离最短(即下图黄色框选区域)
如果点多一些,我们扩展以下:
会发现:
奇数个时候,取中位数刚合适(取紫色区域中间);偶数取到中间两个数直接就可以。
根据数学表达式,我们发现的确满足取等条件,则说明正确。
核心代码:
res += abs(q[i] - q[n / 2])
为啥能直接写:因为不论奇数偶数,取到q[n/2]即可,编译器会自动取整。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
sort(a, a + n);
int res = 0;
for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[n / 2]);
printf("%d\n", res);
return 0;
}