货仓选址

题目 货仓选址

image-c0e8cc14

思路分析

一个常识性的问题 若要选两个点的最近位置 肯定是在中间吧

image-6ce0f7b6

那拓展成多个点 如果是三角形的话可能就得取垂直平分线了 可是这里还是一维的

那其实到各点距离最短的地方仍是中间位置

分情况讨论了 如果是奇数个时 中位数只有一个 取它即可 若为偶数个时 中位数有两个 任取一个都行

统一一下 成n/2向下取整

证明：

把A[0]~A[N-1]排序，设货仓在X坐标处，X左侧的商店有P家，右侧的商店有Q家。若P < Q，则每把仓库的选址向右移动1单位距离，距离之和就会变少Q

  • P.同理，若P > Q，则仓库的选址向左移动会使距离之和变小。当P==Q时为最优解。

因此仓库应该建在中位数处，把A进行排序，

当N为奇数时，货仓建在A[(N - 1)/2]处，

当N为偶数时，仓库建在A[(N - 1)/2 + 1]处

image-092b459d

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=100010;

int a[N];

int n;

int main()

{

    cin>>n;

    for(int i=0;i<n;i++)

        cin>>a[i];

    sort(a,a+n);

    int mid=a[n/2];

    LL res=0;

    for(int i=0;i<n;i++)

        res+=abs(a[i]-mid);

    cout<<res;

    return 0;

}

同类题型

视频讲解

⬅️ 最小的和 🏠 00-刷题理模型 ➡️ 区间分组