首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#13170

街道的中心 题目描述 城市商业街主干道是一条笔直的道路,商业街里有 n 家店铺,现给定 n 个店铺的位置,请在这条道路上找到一个中心点,使得所有店铺到这个中心点…

街道的中心

题目描述

城市商业街主干道是一条笔直的道路,商业街里有 n 家店铺,现给定 n 个店铺的位置,请在这条道路上找到一个中心点,使得所有店铺到这个中心点的距离之和最小,并输出这个最小值。

输入格式

第一行:单个正整数 n。

第二行:n 个整数表示一个店铺的位置。

输出格式

单个整数:表示商铺到中心点距离之和的最小值。


输入样例

4  

-2  0  2  0  

输出样例

4

说明提示

数据范围:

· -5000≤xi≤5000

· 对于 30% 的数据,1≤n≤20

· 对于 60% 的数据,1≤n≤2000

· 对于 100% 的数据,1≤n≤100000

样例解释:

最优中心设置在坐标 0 处,总距离为:

∣-2-0∣+∣0-0∣+∣2-0∣+∣0-0∣=2+0+2+0=4

限制

时间限制:1000ms

内存限制:512MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;cmath&gt; using namespace std; int main() {     int n;     cin &gt;&gt; n;          // 读取店铺位置     int* positions = new int[n];     for (int i = 0; i &lt; n; i++) {         cin &gt;&gt; positions[i];     }          // 排序位置数组     sort(positions, positions + n);          // 计算中位数     int mid = positions[n / 2];          // 计算距离之和     long long total = 0;     for (int i = 0; i &lt; n; i++) {         total += abs(positions[i] - mid);     }          cout &lt;&lt; total &lt;&lt; endl;     delete[] positions;     return 0; }</pre>
这道题暂未补解析。