在一条数轴上有N家商店,它们的坐标分别为 A[1]~A[N]。现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。

输入格式

第一行一个整数N,第二行N个整数A[1]~A[N]。

输出格式

一个整数,表示距离之和的最小值。

输入样例:

4
6 2 9 1

输出样例:

12

数据范围 N≤100000, A[i]≤1000000

题目分析

首先, 货仓的选址一定在商店的坐标范围内,

所以我们先将其坐标排序。

假设货仓地址为 p , 货仓左边有 L 个商店, 右边有 R 个商店。

我们可以发现:

  • p + 1, 那么L个商店到货仓的距离 +1, R个商店到货仓的距离 -1 。
  • p - 1, 那么L个商店到货仓的距离 -1, R个商店到货仓的距离 +1 。

假设 L > R, 那么将 p 向左移动是一个好的选择,

假设 L < R, 那么将 p 向右移动是一个好的选择。

但是, 这是 L 和 R 不变的情况下, 实际情况是: 随着 p 的移动, L 、R的值会分别改变。

我们可以发现, 当 L == R 的时候,商店到货仓库的距离之和始终不变。

那么:

  • 对于奇数个商店, 选取其地址的中位数即可。

  • 对于偶数个商店, 选取中间两个商店之间的坐标均可。

代码实现

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, val;
vector <int> arr;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0;  i  < n; ++i) {
        cin >> val;
        arr.push_back(val);
    }
    sort(arr.begin(), arr.end());
    int p = (n & 1 ? arr[((n - 1) >> 1)] : (arr[((n - 1) >> 1)] + arr[(n >> 1)]) >> 1);
    int ans = 0;
    for(auto& t : arr) ans += abs(t - p);
    cout << ans;
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status