问题类型:求多个定点到一个可动点距离之和最小值
数学背景:1.|x - m| + |x - n|型 通过去绝对值易得函数f(x) = |x - m| + |x - n|(m < n) 为以点(m, n - m) (n, n - m)为折点的倒梯形
2.|x - m| - |x - n|型 通过去绝对值易得函数f(x) = |x - m| - |x - n|(m < n) 为以点((m + n)/2 , 0)为 对称中心的“Z”字形
3.a|x - m| + b|x - n|型(a,b为常数) 通过去绝对值易得函数f(x) = a|x - m| + b|x - n|(m < n)以点
(m, f(m)) (n, f(n) )为折点的折线。 a+b>0时有最小值 min (f(m), f(n) ),其他情况有兴趣的同志可 以自己推导
4.sum(i = 1, 2,...,n) | x - ai |, 当n为奇数时函数图像为"V"字形,中点可取最小值
当n为偶数时函数图像为倒梯形,中间平滑段随意取可得最小值
具体问题:
sum(i = 1, 2,...,n) | x - ai |型
在一条数轴上有 n家商店,它们的坐标分别为 A1∼An。
现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。
为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数 n。
第二行 n个整数 A1∼An。
输出格式
输出一个整数,表示距离之和的最小值。
数据范围
1≤N≤100000,
0≤Ai≤40000
输入样例:
46 2 9 1
输出样例:
12
#include<stdio.h>int n, a[100010];void sort(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){do i ++ ; while (q[i] < x);do j -- ; while (q[j] > x);int temp;if (i < j){temp = a[j];a[j] = a[i];a[i] = temp;}}sort(q, l, j);sort(q, j + 1, r);}int main(){scanf("%d", &n);for(int i = 0; i < n; i ++) scanf("%d", &a[i]);sort(a, 0, n - 1);int x_min = 0;for(int i = 0; i < n; i ++)x_min += abs(a[i] - a[n >> 1]);printf("%d", x_min);return 0;}