贪心题：仓库选址

短命女 2023-09-26 18:10 80阅读 0赞

在一条数轴上有 N家商店，它们的坐标分别为 A1∼AN。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

##### **输入格式** #####

第一行输入整数 N。

第二行 N个整数 A1∼AN。

##### **输出格式** #####

输出一个整数，表示距离之和的最小值。

##### **数据范围** #####

1≤N≤100000,

0≤Ai≤40000

##### **输入样例：** #####

4
    6 2 9 1

##### **输出样例：** #####

12

<table style=""> 
 <tbody> 
  <tr> 
   <td style="width:738px;vertical-align:top;height:51px;"><p style=""><span style="font-size:9pt;">难度：<span style="font-weight:bold;">简单</span></span></p></td> 
  </tr> 
  <tr> 
   <td style="width:738px;vertical-align:top;height:51px;"><p style=""><span style="font-size:9pt;">时/空限制：1s / 64MB</span></p></td> 
  </tr> 
  <tr> 
   <td style="width:738px;vertical-align:top;height:51px;"><p style=""><span style="font-size:9pt;">来源：《算法竞赛进阶指南》, 模板题</span></p></td> 
  </tr> 
  <tr> 
   <td style="width:738px;vertical-align:top;height:51px;"><p style=""><span style="font-size:9pt;">算法标签</span></p><p style=""><span style="font-size:9pt;"> 排序快速 选择算法 贪心 绝对值不等式 </span></p></td> 
  </tr> 
 </tbody> 
</table>

#include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int main()
    {
        int n, a[100010];
        long long int res = 0;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        sort(a , a + n);
        int c = a[n / 2];
        for (int i = 0; i < n; i++)
        {
            res += abs(a[i] - c);
        }
        cout << res << endl;
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，80人围观）

还没有评论，来说两句吧...

相关阅读

相关 2023华为OD机试真题【新学校选址】

题目内容为了解新学期学生暴涨的问题,小乐村要建立所新学校考虑到学生上学安全问题,需要所有学生家到学校的距离最短. 假设学校和所有学生家都走在一条直线之上,请问

谁借莪１个温暖的怀抱￠/ 2024年03月22日 09:38/ 0 赞/ 59 阅读

相关【华为机试真题 Python】服务中心选址

题目描述一个快递公司希望在一条街道建立新的服务中心。公司统计了该街道中所有区域在地图上的位置，并希望能够以此为依据为新的服务中心选址：使服务中心到所有区域的距离的总和最

小咪咪/ 2024年02月22日 09:50/ 0 赞/ 49 阅读

相关 Java 华为真题-新学校选址

需求： > 为了解新学期学生暴涨的问题,小乐村要建立所新学校，考虑到学生上学安全问题,需要所有学生家到学校的距离最短。假设学校和所有学生家都走在一条直线之上,请问学校建

谁借莪１个温暖的怀抱￠/ 2023年10月15日 22:02/ 0 赞/ 37 阅读

相关贪心题：仓库选址

在一条数轴上有 N家商店，它们的坐标分别为 A1∼AN。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使

短命女/ 2023年09月26日 18:10/ 0 赞/ 81 阅读

相关 2019.12.15CCF第二题回收站选址

2019.12.15CCF第二题回收站选址判断每个点的上下左右是不是都有点，有的话再判断是一到四哪种类型 include<iostream> usi

左手的ㄟ右手/ 2023年06月24日 04:43/ 0 赞/ 13 阅读

相关贪心算法 leetcode编程题

1. [452. 用最少数量的箭引爆气球][452.] 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐

ゝ一世哀愁。/ 2022年12月23日 09:55/ 0 赞/ 187 阅读

相关算法刷题记三（贪心）

文章目录分发饼干（8/2-455）无重叠区间（8/3-435）分发饼干（8/2-455） ![在这里插入图片描述][waterma

迈不过友情╰/ 2022年09月02日 08:12/ 0 赞/ 155 阅读

相关贪心的一道题 Supermarket

POJ 1456 描述 A supermarket has a set Prod of products on sale. It earns a profit px for

痛定思痛。/ 2022年06月13日 09:19/ 0 赞/ 155 阅读

相关邮局选址问题

![这里写图片描述][70] import java.util.; //邮局选址问题 public class PostOfficeArr{

た入场券/ 2022年05月26日 05:51/ 0 赞/ 168 阅读

相关社区医院选址问题

问题描述 n个社区之间的交通图用有向加权图表示，先要从这n个社区中选择一个社区建立一所医院，问这所医院应建在那个社区，能使所有的社区都离这家医院比较近（能使离医院最远的社

约定不等于承诺〃/ 2022年05月23日 13:38/ 0 赞/ 175 阅读