曼哈顿距离与动态规划在选址问题中的应用

1. 问题背景与理解

第一次看到这个题目时，我想起了小时候在农村生活的场景。村里每隔一段距离就有一个小卖部，村民们需要步行去购买日用品。如果小卖部的位置选得不好，住在远处的村民就要走很远的路。这个问题本质上就是在寻找一个最优位置，使得所有人的"步行成本"最低。

从专业角度来看，这是一个典型的选址问题(Location Problem)，属于运筹学中的经典模型。题目要求我们在一条直线上分布的n个村庄中选择一个位置建立快递站，使得所有村庄的"人口×距离"之和最小。这种加权距离和在数学上被称为曼哈顿距离(Manhattan Distance)的加权和。

提示：曼哈顿距离在二维空间是|x1-x2| + |y1-y2|，在一维空间简化为两点坐标差的绝对值。

2. 暴力枚举法详解

2.1 算法思路

暴力法就像是一个勤勤恳恳的邮递员，他会亲自跑到每个可能的位置，计算如果把快递站建在这里，所有人的取件成本总和是多少。然后比较所有位置的结果，选择成本最低的那个。

具体步骤：

1. 遍历每个村庄位置k（从1到n）
2. 对于每个k，计算所有村庄i到k的加权距离和：Σ w[i] * |i - k|
3. 记录所有k中计算得到的最小值

2.2 代码实现与解析

让我们仔细看看代码实现，特别是几个关键点：

cpp复制#include <iostream>
#include <cstdlib>  // 包含abs()函数
using namespace std;

int main() {
    int n;
    cin >> n;
    int w[105];  // 存储各村庄人口
    
    // 输入人口数据
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }

    int min_sum = INT_MAX;  // 初始化为最大整数值
    
    // 枚举每个可能的位置k
    for (int k = 1; k <= n; k++) {
        int current_sum = 0;
        
        // 计算位置k的总成本
        for (int i = 1; i <= n; i++) {