题解：P11848 [TOIP 2023] 房屋推荐

zhengddzz · 2025-03-07 12:57:44 · 题解

不要再怀疑我是不是 AI 了！！！

算法思路

这道题目要求我们根据房屋到最近地铁站的距离、租金和编号进行多条件排序。可以通过以下步骤解决这道题目：

1. 最近距离计算：对每个房屋遍历所有地铁站，计算欧式距离平方的最小值（防止浮点运算）。
2. 稳定排序：使用自定义排序规则依次比较距离、租金、编号。
3. 输入输出优化：使用快速输入输出方法处理大规模数据。

复杂度分析

• 时间复杂度：O(nm + n\log n)，其中 n 是房屋数量，m 是地铁站数量。每个房屋需遍历所有地铁站计算距离，最后进行快速排序。

• 空间复杂度：O(n)，需要存储所有房屋的信息，n 意思如上。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

struct House {
    int a, b, r, id;
    ll min_dist_sq = 9e18; // 初始化为极大值
};

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

    // 读取输入
    int n, m;
    cin >> n >> m;

    vector<House> houses(n);
    for (int i = 0; i < n; ++i) {
        auto& h = houses[i];
        cin >> h.a >> h.b >> h.r;
        h.id = i + 1; // 编号从1开始
    }

    vector<pair<int, int>> stations(m);
    for (auto& s : stations) {
        cin >> s.first >> s.second;
    }

    // 计算每个房屋到所有地铁站的最小距离平方
    for (const auto& [c, d] : stations) {
        for (auto& h : houses) {
            ll dx = h.a - c;
            ll dy = h.b - d;
            ll dist_sq = dx*dx + dy*dy;
            if (dist_sq < h.min_dist_sq) {
                h.min_dist_sq = dist_sq;
            }
        }
    }

    // 自定义排序规则
    sort(houses.begin(), houses.end(), [](const House& x, const House& y) {
        if (x.min_dist_sq != y.min_dist_sq) 
            return x.min_dist_sq < y.min_dist_sq;
        if (x.r != y.r)
            return x.r < y.r;
        return x.id < y.id;
    });

    // 输出结果
    for (const auto& h : houses) {
        cout << h.id << '\n';
    }

    return 0;
}

关键点

• 避免浮点运算：通过比较距离平方替代实际距离，既避免精度误差又提升运算速度。
• 快速输入输出：使用了 ios::sync_with_stdio(false) 和 cin.tie(0) 加速输入输出。
• 原地更新最小值：遍历地铁站时直接更新最小距离，不用存储中间结果。

示例分析

以题目样例 1 输入为例：

3 3
2 0 11000
5 0 12000
3 3 10000
1 3
3 0
5 3

计算过程：

1. 房屋 1 到地铁站 2 的平方距离最小为 1。
2. 房屋 3 到两个地铁站的平方距离均为 4，但租金更优。
3. 最终排序结果为 1 → 3 → 2。