题解 | #货仓选址#

一种前缀和的解法

假如我们并不知道中位数就是最优解

先看暴力枚举的思路

1-index数组a存储货仓的坐标 先给a排个序

for i := 1 to n

a[i]距离左边货仓j: a[i] - a[j]

距离左边所有货仓就是 a[i] - (a[1] + a[2] +... + a[i - 1])

不难发现，优化后面的sum(a[1], a[i - 1])可以用前缀和解决

即a[i]距它左边所有货仓的总距离就是a[i] - prefix[i - 1];

同理a[i]的右侧就是(prefix[n] - prefix[i]) - (n - i) * a[i];

看数据范围，很容易爆int，记得开longlong

下面是AC代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n;
  cin >> n;
  int a[n + 1];

  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }

  sort(a + 1, a + n + 1);

  int prefix[n + 1] = {};
  for (int i = 1; i <= n; ++i) {
    prefix[i] = prefix[i - 1] + a[i];
  }

  ll res = numeric_limits<ll>::max();
  for (int i = 1; i <= n; ++i) {
    ll dist = (ll)(i - 1) * a[i] - prefix[i - 1];
    dist += prefix[n] - prefix[i] - (ll)(n - i) * a[i];
    res = min(res, dist);
  }

  cout << res << endl;
  return 0;
}