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

版块：网络百科类型：普通作者：某个人查看：21 回复：0 获赞：0 时间：2025-07-15 14:39:51

截图未命名.jpg 算法竞赛实战：洛谷P1293城市选址问题的加权中位数解法洛谷洛谷题解算法竞赛 C++代码第1张

一、问题描述与解题思路

洛谷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;
}