题解：P10452 货仓选址

abc1856896 · 2024-05-16 14:01:14 · 题解

题目描述

在数轴上给出 n 个点。

有一个点使得这个点到所有其他点的距离最小，求这个距离。

solution

简单贪心。

最优的点应该是在中间的点，因此我们排完序后取中间点即可。

时间复杂度 O(n \log n)。

code

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    int t=a[n/2];
    for(int i=1;i<=n;i++) {
        ans+=abs(a[i]-t);
    }
    cout<<ans;
    return 0;
}