A26394. 街道的中心
填空题
困难
知识点
题目描述
街道的中心
题目描述
城市商业街主干道是一条笔直的道路，商业街里有 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
参考答案
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
int a[100010]={0};
int sum=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int x=0;
int y=n-1;
while(x<y)
{
sum+=(a[y]-a[x]);
x++;
y--;
}
cout<<sum;
return 0;
}
上一题
下一题