算法基础之货仓选址

本文主要是介绍算法基础之货仓选址，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

货仓选址

• 核心思想： 贪心

  • 绝对值不等式 : $|x–a|+|x–b|\ge |a–b|$

  • 将n个数两两分组 1~~ n-1 (奇数会剩一个) 分别用绝对值不等式 即可推出来

    • 货仓位置应该在中位数上(奇数) 或在中间两数之间(包括端点)(偶数)
    • 

  •   #include<iostream>#include<algorithm>using namespace std;typedef long long LL;const int N = 100010;int n;int a[N];int main(){cin>>n;for(int i=0;i<n;i++) cin>>a[i];sort(a,a+n);  //拍完序找中位数LL res = 0;for(int i=0;i<n;i++) res += abs(a[i] - a[n/2]);  //距离 n/2是中位数(取整)下标//写成i/2也可以过 二者等价 res += a[i] - a[i/2] 不用写绝对值cout<<res<<endl;}
    

这篇关于算法基础之货仓选址的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---