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

ftggdnt

一、问题描述与解题思路

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

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

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. #include <climits>
   
5. using namespACe std;
   
6. 
   
7. // 城市结构体，包含学生人数、距离和名称
   
8. struct City {
   
9.     int students;
   
10.     int distance;
    
11.     string name;
    
12.    
    
13.     // 构造函数处理输入格式
    
14.     City() {
    
15.         cin >> students >> distance;
    
16.         while(cin.peek() == ' ') cin.get();  // 跳过多余空格
    
17.         getline(cin, name);
    
18.         // 处理Windows换行符
    
19.         if(!name.empty() && name.back() == '\r')
    
20.             name.pop_back();
    
21.     }
    
22. };
    
23. 
    
24. int main() {
    
25.     vector<City> cities;
    
26.     // 特殊处理莫斯科必为**一条记录
    
27.     while(true) {
    
28.         City city;
    
29.         if(cin.fail()) break;
    
30.         cities.push_back(city);
    
31.         if(city.distance == 0) break;  // 莫斯科距离为0，作为结束标志
    
32.     }
    
33.    
    
34.     // 按距离排序确保莫斯科在**
    
35.     sort(cities.begin(), cities.end(), [](const City& a, const City& b) {
    
36.         return a.distance < b.distance;
    
37.     });
    
38.    
    
39.     // 计算总学生数
    
40.     int total = 0;
    
41.     for(auto& c : cities) total += c.students;
    
42.    
    
43.     // 寻找加权中位数位置
    
44.     int median_pos = 0;
    
45.     int count = 0;
    
46.     for(; median_pos < cities.size(); ++median_pos) {
    
47.         count += cities[median_pos].students;
    
48.         if(count * 2 >= total) break;  // 找到满足条件的**个位置
    
49.     }
    
50.    
    
51.     // 计算最小总花费（允许有多个候选城市）
    
52.     vector<int> candidates;
    
53.     int min_cost = INT_MAX;
    
54.     for(int i = 0; i < cities.size(); ++i) {
    
55.         int cost = 0;
    
56.         for(auto& c : cities)
    
57.             cost += abs(c.distance - cities[i].distance) * c.students;
    
58.         
    
59.         if(cost < min_cost) {
    
60.             min_cost = cost;
    
61.             candidates.clear();
    
62.             candidates.push_back(i);
    
63.         } else if(cost == min_cost) {
    
64.             candidates.push_back(i);
    
65.         }
    
66.     }
    
67.    
    
68.     // 选择距离莫斯科最近的城市（当有多个候选时）
    
69.     int best = 0;
    
70.     for(int i = 1; i < candidates.size(); ++i)
    
71.         if(cities[candidates[i]].distance < cities[candidates[best]].distance)
    
72.             best = i;
    
73.    
    
74.     cout << cities[candidates[best]].name << " " << min_cost << endl;
    
75.     return 0;
    
76. }

复制代码

三、算法核心解析

• 输入处理：
  
  
  • 使用City结构体处理输入数据，特别处理了Windows换行符问题
  • 莫斯科作为特殊城市（距离为0）作为输入结束标志
    
    
• 数据预处理：
  
  
  • 按距离排序城市，确保莫斯科在**
  • 计算总学生数，为加权中位数计算做准备
    
    
• 加权中位数计算：
  
  
  • 遍历排序后的城市列表，累加学生数直到达到总学生数的一半
  • 这个位置就是**候选位置之一
    
    
• 精确计算**解：
  
  
  • 计算每个候选城市的总交通成本
  • 找出最小成本的所有候选城市
  • 当有多个候选时，选择距离莫斯科最近的城市
    
    

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

• 时间复杂度：
  
  
  • 排序操作：O(n log n)
  • 加权中位数查找：O(n)
  • 精确计算：O(n²)
  • 总体复杂度：O(n²)
    
    
• 优化建议：
  
  
  • 可以利用加权中位数性质，只计算中位数附近的几个候选点
  • 对于大规模数据，可以考虑分治算法
  • 可以预处理距离差值，减少重复计算
    
    
• 边界条件处理：
  
  
  • 处理空输入情况
  • 处理所有城市学生数为0的特殊情况
  • 处理多个城市距离相同的情况
    
    

来源：大矩学习资料