班级聚会

题意

给出若干个城市的人数、到莫斯科的距离和城市名。要求从这些城市中选一个举办聚会，使所有同学前往该城市的总路程最小；若并列，选更靠近莫斯科的城市。

思路

先看一个可以直接验证想法的朴素解：

枚举每个城市作为会场，直接计算所有人的总代价。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#include <bits/stdc++.h>
using namespace std;

struct City {
    long long cnt;
    long long pos;
    string name;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<City> a;
    City c;
    while (cin >> c.cnt >> c.pos >> c.name) {
        a.push_back(c);
    }

    long long best_cost = (1LL << 62);
    string best_name;
    long long best_pos = 0;

    for (auto &center : a) {
        long long cost = 0;
        for (auto &it : a) {
            cost += it.cnt * llabs(it.pos - center.pos);
        }
        if (cost < best_cost || (cost == best_cost && center.pos < best_pos)) {
            best_cost = cost;
            best_name = center.name;
            best_pos = center.pos;
        }
    }

    cout << best_name << ' ' << best_cost << '\n';
    return 0;
}

这题的本质是一维带权中位数。把城市位置看成数轴点，把人数看成权重。

按距离排序后，当前缀人数第一次达到总人数一半时，这个位置就是最优会场。如果有多个位置都最优，最左边那个正好也满足“更靠近莫斯科优先”。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42#include <bits/stdc++.h>
using namespace std;

struct City {
    long long cnt;
    long long pos;
    string name;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<City> a;
    City c;
    while (cin >> c.cnt >> c.pos >> c.name) {
        a.push_back(c);
    }

    sort(a.begin(), a.end(), [](const City &lhs, const City &rhs) {
        if (lhs.pos != rhs.pos) return lhs.pos < rhs.pos;
        return lhs.name < rhs.name;
    });

    long long total = 0;
    for (auto &it : a) total += it.cnt;

    long long pref = 0;
    for (auto &it : a) {
        pref += it.cnt;
        if (pref * 2 >= total) {
            long long cost = 0;
            for (auto &jt : a) {
                cost += jt.cnt * llabs(jt.pos - it.pos);
            }
            cout << it.name << ' ' << cost << '\n';
            return 0;
        }
    }

    return 0;
}

复杂度

时间复杂度 $O(n log n)$ ，空间复杂度 $O(n)$ 。

总结

这题的关键是把“最小化总路程”识别成带权中位数问题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

代码

复杂度

总结

一图流解析