优化货仓选址：最小化商店距离之和问题

"该资源是一个关于算法题解的文件，主要讨论了如何在数轴上选择货仓位置，以最小化货仓到各商店距离之和的问题。" 在这道算法题中，我们面临的任务是在一条数轴上为N家商店选择一个理想的货仓位置，目标是使货仓到所有商店的距离之和最小。这个问题属于经典的数学优化问题，可以通过计算中位数来解决。 首先，我们需要了解输入格式。输入包含两部分：第一行是一个整数N，表示商店的数量；第二行是N个整数，依次表示每个商店在数轴上的坐标A₁, A₂, ..., A_N。所有坐标值都在0到40000之间。 接下来是输出格式，应输出一个整数，表示距离之和的最小值。 解题的关键在于找到一个中心点，使得从这个点到所有点的距离之和最小。在数轴上，这个中心点通常是所有坐标排序后的中位数。这是因为中位数将坐标集分成两个相等大小（或相差1）的部分，这样可以尽可能地平衡货仓到两侧商店的距离。 给出的参考C++代码实现如下： ```cpp #include <bits/stdc++.h> using namespace std; const int N = 100100; int a[N], n, i, ans, sum; int main() { cin >> n; for (i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + 1 + n); // 对坐标进行排序 int sm = a[n / 2 + 1]; // 计算中位数 for (i = 1; i <= n; i++) ans = ans + abs(a[i] - sm); // 计算每个坐标与中位数的绝对差并累加 cout << ans; return 0; } ``` 这段代码首先读入商店数量和坐标，然后对坐标进行排序。之后，它找出中位数`sm`，并通过遍历所有坐标，计算每个坐标与中位数的绝对值差并累加，最后输出这个总和作为答案。 这个算法的时间复杂度为O(N log N)，主要花费在排序上。空间复杂度为O(N)，用于存储商店坐标。由于N的最大值为100000，这个算法在给定的数据范围内是可行的。通过利用中位数的性质，我们可以快速找到一个优化的位置，从而有效解决货仓选址问题。