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

思路

这道题思路很简单，但是坑比较多。

首先第一个坑点就是sqrt函数的精度问题，解决这个问题还是比较简单的，我们不sqrt就可以了。

因为我们开不开方对于我们距离的大小关系是没有任何影响的，在这个问题我们不需要知道距离的精确值，大小关系才是我们需要的东西。

但是我们的另一个问题就出来了，

a_i

以及

b_i

的值最大会到

10^5

，很显然，我们用int是存不下根据公式算出来的值的，这个问题也很好解决，开long long即可。

我们遍历每一个地铁站和房屋的配对，计算出每个房屋与距离最近的地铁站之间的距离，最后再根据题意对所有房屋进行排序，我们这道题就可以解决了。

AC 代码

CPP

#include<bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
#define il inline
#define int long long

using namespace std;
using ll = long long;
using ull = unsigned long long;

const int maxn = 1e5+10;
const int maxm = 1e3+10;

int n,m;

struct h{
    int id,x,y,r,d;
}a[maxn];

struct s{
    int x,y,d;
}b[maxm];

il int dis(int i,int x,int y){return(a[i].x-x)*(a[i].x-x)+(a[i].y-y)*(a[i].y-y);}

il bool cmp(const h &x,const h &y){
    if(x.d != y.d)return x.d < y.d;
    if(x.r != y.r)return x.r < y.r;
    return x.id < y.id;
}

signed main(){
	// freopen("test.in","r",stdin);
	// freopen("test.out","w",stdout);
	ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);

    cin>>n>>m;
    for(int i = 1;i <= n;i++){
        cin>>a[i].x>>a[i].y>>a[i].r;
        a[i].id = i;
        a[i].d = LLONG_MAX;
    }
    for(int i = 1;i <= m;i++)cin>>b[i].x>>b[i].y;

    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            a[i].d = min(a[i].d,(a[i].x - b[j].x)*(a[i].x - b[j].x) + (a[i].y - b[j].y)*(a[i].y - b[j].y));
        }
    }
    sort(a+1,a+1+n,cmp);
    for(int i = 1;i <= n;i++)cout<<a[i].id<<'\n';
	return 0;
}

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

文章操作

思路

AC 代码

相关推荐

评论

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