算法基础之货仓选址

2024-01-07 17:13:26

货仓选址

  • 核心思想: 贪心

    • 绝对值不等式 : ∣ x – a ∣ + ∣ x – b ∣ ≥ ∣ a – b ∣ |x – a| + |x – b| ≥ |a – b| xa+xbab

    • 将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;
        }
      

文章来源:https://blog.csdn.net/Pisasama/article/details/135440039
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。