算法竞赛实战：洛谷P1293城市选址问题的加权中位数解法

一、问题描述与解题思路

洛谷P1293题目要求我们为多个城市选择一个最佳的集会地点，使得所有学生前往该地点的总交通成本最低。每个城市有三个属性：学生人数、距离莫斯科的距离（题目规定莫斯科距离为0）以及城市名称。这是一个典型的设施选址问题，可以通过加权中位数算法高效解决。

二、完整代码实现（带详细注释）

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespACe std;

// 城市结构体，包含学生人数、距离和名称
struct City {
    int students;
    int distance;
    string name;
    
    // 构造函数处理输入格式
    City() {
        cin >> students >> distance;
        while(cin.peek() == ' ') cin.get();  // 跳过多余空格
        getline(cin, name);
        // 处理Windows换行符
        if(!name.empty() && name.back() == '\r')
            name.pop_back();
    }
};

int main() {
    vector<City> cities;
    // 特殊处理莫斯科必为最后一条记录
    while(true) {
        City city;
        if(cin.fail()) break;
        cities.push_back(city);
        if(city.distance == 0) break;  // 莫斯科距离为0，作为结束标志
    }
    
    // 按距离排序确保莫斯科在最后
    sort(cities.begin(), cities.end(), [](const City& a, const City& b) {
        return a.distance < b.distance;
    });
    
    // 计算总学生数
    int total = 0;
    for(auto& c : cities) total += c.students;
    
    // 寻找加权中位数位置
    int median_pos = 0;
    int count = 0;
    for(; median_pos < cities.size(); ++median_pos) {
        count += cities[median_pos].students;
        if(count * 2 >= total) break;  // 找到满足条件的第一个位置
    }
    
    // 计算最小总花费（允许有多个候选城市）
    vector<int> candidates;
    int min_cost = INT_MAX;
    for(int i = 0; i < cities.size(); ++i) {
        int cost = 0;
        for(auto& c : cities)
            cost += abs(c.distance - cities[i].distance) * c.students;
        
        if(cost < min_cost) {
            min_cost = cost;
            candidates.clear();
            candidates.push_back(i);
        } else if(cost == min_cost) {
            candidates.push_back(i);
        }
    }
    
    // 选择距离莫斯科最近的城市（当有多个候选时）
    int best = 0;
    for(int i = 1; i < candidates.size(); ++i)
        if(cities[candidates[i]].distance < cities[candidates[best]].distance)
            best = i;
    
    cout << cities[candidates[best]].name << " " << min_cost << endl;
    return 0;
}

三、算法核心解析

1. 输入处理：

• 使用City结构体处理输入数据，特别处理了Windows换行符问题

• 莫斯科作为特殊城市（距离为0）作为输入结束标志

2. 数据预处理：

• 按距离排序城市，确保莫斯科在最后

• 计算总学生数，为加权中位数计算做准备

3. 加权中位数计算：

• 遍历排序后的城市列表，累加学生数直到达到总学生数的一半

• 这个位置就是最优候选位置之一

4. 精确计算最优解：

• 计算每个候选城市的总交通成本

• 找出最小成本的所有候选城市

• 当有多个候选时，选择距离莫斯科最近的城市

四、复杂度分析与优化建议

1. 时间复杂度：

• 排序操作：O(n log n)

• 加权中位数查找：O(n)

• 精确计算：O(n²)

• 总体复杂度：O(n²)

2. 优化建议：

• 可以利用加权中位数性质，只计算中位数附近的几个候选点

• 对于大规模数据，可以考虑分治算法

• 可以预处理距离差值，减少重复计算

3. 边界条件处理：

• 处理空输入情况

• 处理所有城市学生数为0的特殊情况

• 处理多个城市距离相同的情况