P8073 [COCI 2009/2010 #7] BAKICE

· · 题解

最近切了好多 COCI 的水题。

题目暗含了一个处理顺序，即按照所有乘客到椅子的最短距离升序处理。那么预处理一下所有乘客到椅子的欧几里得距离，最多只有 10^4 组，然后按照距离排序。

处理时，如果当前乘客已入座则跳过，如果当前椅子无人就记录入座的人离它的距离。后面如果遇到同一距离，则为一次爆炸，记录一下。

注意距离不要开根号，有精度问题，按平方处理即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 10005;

struct node{
    int u, v, d;
    bool operator<(node p) const{
        return d < p.d;
    }
} g[N];

int r, c, uc, vc, ec, st[N], us[N];
pair<int, int> uu[N], vv[N];

int dist(int x1, int y1, int x2, int y2){
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> r >> c;
    for(int i = 1; i <= r; ++ i)
        for(int j = 1; j <= c; ++ j){
            char ch;
            cin >> ch;
            if(ch == 'X')
                uu[++ uc] = make_pair(i, j);
            if(ch == 'L')
                vv[++ vc] = make_pair(i, j);
        }
    for(int i = 1; i <= uc; ++ i)
        for(int j = 1; j <= vc; ++ j)
            g[++ ec] = {i, j, dist(uu[i].first, uu[i].second, vv[j].first, vv[j].second)};
    sort(g + 1, g + ec + 1);
    int ans = 0;
    for(int i = 1; i <= ec; ++ i){
        int u = g[i].u, v = g[i].v, d = g[i].d;
        if(st[u]) continue;
        if(!us[v]) us[v] = d, st[u] = 1;
        else if(us[v] == d) ++ ans, st[u] = 1, us[v] = -1;
    }
    cout << ans;

    return 0;
}