充电桩（move）- 2024庐阳区初中组T4

题目描述

有n个电子狗在步行街一些位置表演，这些位置是确定的，等到夜深人静，他们回到某一个充电桩充电。为了建设成本最小化，n个充电桩必须建在步行街连续的一段，间隔为1个单位的距离。一个充电桩只能供一个电子狗充电。

给定电子狗在步行街表演的位置，现在的问题：如何建设充电桩，使得电子狗找到充电桩行走的总距离最短。求这个最小值（多少个单位距离）。

输入格式

第一行，一个整数n。

第二行，n个整数，第i个数Xi表示第i个电子狗在步行街表演的位置。

输出格式

一个整数，表示n个电子狗充电移动的总距离的最小值。

输入输出样例

输入：

3 9 2 6

输出：

5

说明

数据范围

N<=100000

-10^9<=Xi<=10^9

解析：

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll a[100010]; int main() { ll n; cin >> n; for(ll i=1;i<=n;i++)cin >> a[i]; sort(a+1,a+n+1); ll pos,first; if(n%2==1) { pos =a[n/2+1]; first=pos-n/2; } else if(n%2==0) { pos=(a[n/2]+a[n/2+1])/2; first=pos-n/2-1; } ll ans=0; for(ll i=1;i<=n;i++) { ans+=abs(a[i]-first); first++; } cout << ans; return 0; }