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

ryf2011 · 2025-03-06 13:09:19 · 题解

题目思路

我们用一个结构体记录每个房屋的坐标、月租、离地铁站最短距离和编号。

全部输入完成后，对于每个房屋，我们都遍历一遍地铁坐标数组，取最小值。由于本题 n \le 10^5,m \le 10^3，所以 \mathcal O(nm) 的时间复杂度不会超时。

接下来按照题目要求排序，最后输出编号即可。

注意一点，计算距离是涉及转换小数，本题要求开 \texttt{long double} 存储。

代码

注：本代码仅供参考。具体见 提交记录。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
#define double long double //一定要开 long double！
using namespace std;
const int max_n=1e5+5;
const int max_m=1e3+5;
int n,m,c[max_m],d[max_m];
struct node{ //结构体
    int id; //编号
    int ha,hb; //坐标
    int r; //月租
    double sl; //距离（小数！）
} houses[max_n];
bool cmp(node a,node b){ //比较函数
    if(a.sl==b.sl){ //如果距离相同，比较月租
        if(a.r==b.r){ //月租相同，比较编号
            return a.id<b.id;
        }
        else{
            return a.r<b.r;
        }
    }
    else{
        return a.sl<b.sl;
    }
}
signed main(){
    //输入
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld %lld %lld",&houses[i].ha,&houses[i].hb,&houses[i].r);
        houses[i].id=i;
    }
    for(int i=1;i<=m;i++){
        scanf("%lld %lld",&c[i],&d[i]);
    }
    //计算、排序
    for(int i=1;i<=n;i++){
        houses[i].sl=sqrt((double)((houses[i].ha-c[1])*(houses[i].ha-c[1])+(houses[i].hb-d[1])*(houses[i].hb-d[1]))); //等同于把 houses[i].sl 初始化为无穷大
        for(int j=2;j<=m;j++){ //houses[i].sl 取最小值
            houses[i].sl=min(houses[i].sl,sqrt((double)((houses[i].ha-c[j])*(houses[i].ha-c[j])+(houses[i].hb-d[j])*(houses[i].hb-d[j])))); //记得转为小数！
        }
    }
    sort(houses+1,houses+n+1,cmp); //按照 cmp 排序
    for(int i=1;i<=n;i++){ //输出编号
        printf("%lld\n",houses[i].id);
    }
    return 0;
}

后记

更多内容，请移步至 \color{red}\texttt{ryf2011}。