洛谷1293题解析：加权中位数城市选址问题的C++解法
一、题目解读
洛谷1293题要求解决一个城市选址问题：给定多个城市的学生人数与到莫斯科的距离，需找到一个城市作为中心点，使得所有学生到该中心的加权距离之和最小。题目输入包含城市名称、学生数和到莫斯科的单向距离，莫斯科本身作为终点（距离为0），需处理特殊输入格式（如Windows换行符）。输出为最优城市的名称及最小总距离。
二、解题思路
1. 关键洞察：总距离最小化的位置必定是某个城市，而非中间点，因此可通过枚举所有城市作为中心点计算总花费。
2. 优化方向：利用加权中位数特性，快速定位候选位置。
3. 贪心选择：在多个最小花费位置中，优先选择距离莫斯科最近的城市，确保结果唯一性。
三、解题步骤
1. 数据输入与预处理
定义City结构体存储学生数、距离和名称。
使用getline处理带空格的城市名，并特殊处理Windows换行符（末尾\r字符）。
通过cin.fail()判断输入结束，确保莫斯科为最后一条记录。
2. 排序与总学生数计算
按距离升序排序，确保莫斯科位于数组末尾（距离0）。
遍历累加所有城市的学生数，得到总人数total。
3. 寻找加权中位数位置
二分查找思想：从左到右遍历城市，累计学生数count，当count*2≥total时，当前城市为加权中位数候选位置。
该位置保证两侧学生数权重均衡，总距离最小。
4. 计算最小总花费并筛选候选城市
遍历每个城市i，计算其作为中心点的总花费（Σ|city[i].distance - city[j].distance| * city[j].students）。
维护最小花费min_cost及候选位置列表candidates，若新花费更小则更新，相同则加入列表。
5. 贪心选择最优城市
在候选列表中，选择距离莫斯科最近（即排序后下标最小）的城市作为最终答案。
四、代码与注释
#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;
}五、总结
本解法通过结合加权中位数的数学性质与贪心策略，将复杂选址问题转化为线性时间复杂度的高效求解。代码中巧妙处理了输入格式兼容性（如Windows换行符）与莫斯科的特殊位置，确保算法的鲁棒性。关键点在于理解“中位数位置即为最优解候选”这一核心逻辑，并通过枚举验证候选点的总花费。该思路对同类加权选址问题具有通用性，适合竞赛选手与编程学习者掌握。
原创内容 转载请注明出处
