配对相减即答案
完全和前缀和及差分(从某题单来的)无关系的简答题
从样例得思路:
1)排序,得 1 2 6 9
2)重点:由题意可知仓库和某商家可以在同一坐标
3)无论仓库建在哪里,仓库到 >排序后第i个坐标< 以及到 >排序后第n-i-1个坐标<,
这两段距离的和是与仓库位置无关的,即距离等于a[r] - a[l]
4)由此,我们只需要将数组排序后头和尾两两配对,这些对的差的累计即为答案
5)若数组有奇数个,那么配对后将剩一个单的...
但是!!! 由第二点2),我们可以将仓库建在这个剩余商家的坐标上,这与前面的答案是不冲突的
于是仓库到剩余这个点的距离为0
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
int ans = 0, l = 0, r = n - 1;
while (l < r)
ans += a[r--] - a[l++];
cout << ans;
return 0;
}