快递中转点，大街分布着密麻的店铺

在笔直的丽水大街上，分布着密麻的店铺，每天有成千上万笔快递订单。小明想开个快递中转点，那每天一定能赚不少钱。每笔订单必须当天送达指定店铺。为了简化问题，小明认为所有店铺都在一条坐标轴上，并且每个店铺都在轴上有一个坐标，每天他都会把所有快递放在一个中转点上，然后一件一件开始派送。可是小明是个懒人，他想尽可能少走路。他的快递中转点开在什么位置(位置可以是轴上任意点，也可以和店铺位置重合)，能使得中转点到所有店铺的距离之和的最小。那么就请你和小明一起解决一下这个小问题吧，找到这个最小值。
Input
第一行一个整数

N表示在轴上共有

N个店铺需要送达快递。
接下来

N行，每行一个整数

[

]
a[i]，表示每个店铺的位置。
Output
包含一个整数，中转站到所有店铺的距离之和的最小值。
Sample Input
5
0
20
40
10
30
Sample Output
60
Sample Explanation
快递中转站建立在
20
20的位置，则到
5
5个点的距离分别是
20
，
0
，
20
，
10
，

#include <iostream>
#include <algorithm>
using namespace std;

int main() 
{
    int N;
    cin >> N;

    int pos[1000];
    for (int i = 0; i < N; i++) {
        cin >> pos[i];
    }

    sort(pos, pos + N);

    int pt = pos[N / 2];

    int total = 0;
    for (int i = 0; i < N; i++) {
        total += abs(pos[i] -pt);
    }

    cout << total << endl;

    return 0;
}

【以下回答由 GPT 生成】

解决方案

为了找到最小距离和，可以使用贪心算法。贪心算法的思路是，在每一步都选择最优的解决方案，并且认为这个选择在整个问题中是最优的。

以下是解决该问题的具体步骤：

1. 读取输入的整数N，表示轴上共有N个店铺。

2. 创建一个长度为N的数组locations，用于存储每个店铺的位置。

3. 依次读取N行输入，将每个店铺的位置保存在locations数组中。

4. 对locations数组进行排序，以便从小到大访问店铺。

python locations.sort()

1. 定义一个变量total_distance，用于存储中转点到所有店铺的距离之和。

2. 定义一个变量transit_point，用于存储中转点的位置。初始值可以设为locations[N//2]，即中间位置的店铺。

3. 遍历locations数组，计算中转点到每个店铺的距离，并将距离累加到total_distance中。

python for location in locations: distance = abs(location - transit_point) total_distance += distance

1. 输出total_distance，表示中转点到所有店铺的距离之和的最小值。

python print(total_distance)

完整的代码示例：

N = int(input())

locations = []
for _ in range(N):
    location = int(input())
    locations.append(location)

locations.sort()

total_distance = 0
transit_point = locations[N // 2]

for location in locations:
    distance = abs(location - transit_point)
    total_distance += distance

print(total_distance)

该解决方案的时间复杂度为O(NlogN)，其中N为店铺的数量。

【相关推荐】

• 你可以看下这个问题的回答https://ask.csdn.net/questions/643479