简答题
偏难
#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 <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
// 读取店铺位置
int* positions = new int[n];
for (int i = 0; i < n; i++) {
cin >> positions[i];
}
// 排序位置数组
sort(positions, positions + n);
// 计算中位数
int mid = positions[n / 2];
// 计算距离之和
long long total = 0;
for (int i = 0; i < n; i++) {
total += abs(positions[i] - mid);
}
cout << total << endl;
delete[] positions;
return 0;
}</pre>
这道题暂未补解析。