杂题

不知道扔哪的题就扔这

大概是个乱搞专题(

CF1651D

给你$n$个点，对每个点找曼哈顿距离最近的没有被占用的点

sol:

考虑到一个点最近的空点的出现

考虑从左往右，我们贪心的想，我们肯定是一直往四个方向bfs，直到遇到一个空点为止

但是如果对每个有的点都这么做一遍显然会T飞

于是我们反过来做，考虑用空点去扩展。

考虑到空点附近一定有一个有的点

所以可以从周围有空点的有的点开始，遍历所有有的点，做一遍bfs即可。

#include
using namespace std;
int dx[]={0,1,-1,0,0};
int dy[]={0,0,0,1,-1};
pair<int,int>ans[200005]; 
queueint,int> >bfs;
pair<int,int> a[200005];
bool vis[200005];
mapint,int>,int>mp;
int N;
int main(){
    scanf("%d",&N);
    for (int i=1;i<=N;i++){
        scanf("%d%d",&a[i].first,&a[i].second);
        mp[a[i]]=i;
    }
    for (int i=1;i<=N;i++){
        for (int j=1;j<=4;j++){
            int x=a[i].first+dx[j],y=a[i].second+dy[j];
            pair<int,int> nww={x,y};
            if (!mp[nww]) {
                vis[i]=1;
                ans[i]=nww;
                break;
            }
        }
        if (vis[i]==1) bfs.push(a[i]);
    }
    while (!bfs.empty()){
        pair<int,int> s=bfs.front();
        bfs.pop();
        if (!mp[s]) continue;
        int x=mp[s];
        for (int j=1;j<=4;j++){
            pair<int,int> nww;
            nww={s.first+dx[j],s.second+dy[j]};
            if (mp[nww] && !vis[mp[nww]]){
                vis[mp[nww]]=1;
                ans[mp[nww]].first=ans[mp[s]].first;
                ans[mp[nww]].second=ans[mp[s]].second;
                bfs.push(nww);
                }
            }
        }
    for (int i=1;i<=N;i++) printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}