P8073 [COCI2009-2010#7] BAKICE 题解

FReQuenter · 2023-08-11 13:50:43 · 题解

发现数据很小。所以基本上随便写写都能过/cf

首先预处理出每个人和每个椅子之间的距离。注意用的是欧几里得距离，别用曼哈顿距离算。

然后来考虑每个人选哪个椅子。这里我们发现，让人去选椅子很麻烦（因为要排序距离）所以直接把所有人到椅子的距离都单独拿出来排序依次处理。这样子一个人选了一个椅子之后就不会动了。

最后统计一下每个椅子被选了多少次。如果大于一次就会炸。然后就做完了。

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
#define sqr(x) ((x)*(x))
using namespace std;
int r,c,cp,cs,ans,cr,sit[25005];
char a[505][505];
pair<int,int> pas[25005],seat[25005],sited[25005];
pair<int,pair<int,int>> ge[25005];
int dis(int x,int y){
    return sqr(pas[x].fi-seat[y].fi)+sqr(pas[x].se-seat[y].se);
}
signed main(){
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>a[i][j];
            if(a[i][j]=='X') pas[++cp]={i,j};
            if(a[i][j]=='L') seat[++cs]={i,j};
        }
    }
    for(int i=1;i<=cp;i++){
        for(int j=1;j<=cs;j++){
            ge[++cr]={dis(i,j),{i,j}};
        }
    }
    sort(ge+1,ge+cr+1);
    for(int i=1;i<=cr;i++){
        if(!sit[ge[i].se.fi]){
            int u=ge[i].se.fi,v=ge[i].se.se;
            if(!sited[v].se) sit[u]=v,sited[v]={u,1};
            else if(dis(u,v)==dis(sited[v].fi,v)) sit[u]=v,sited[v].se++;
        }
    }
    for(int i=1;i<=cs;i++) if(sited[i].se>1) ans++;
    cout<<ans;
}