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

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

算法思路

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

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

复杂度分析

时间复杂度： $O(nm + n\log n)$ ，其中 $n$ 是房屋数量， $m$ 是地铁站数量。每个房屋需遍历所有地铁站计算距离，最后进行快速排序。
空间复杂度： $O(n)$ ，需要存储所有房屋的信息， $n$ 意思如上。

C++ 代码实现

CPP

#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

输入为例：

CPP

计算过程：

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

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

文章操作

算法思路

复杂度分析

C++ 代码实现

关键点

示例分析

相关推荐

评论

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