题解：CF1970B2 Exact Neighbours (Medium)
0tAp
2024-06-11 20:18:23
题目链接：[Exact Neighbours (Medium)](https://www.luogu.com.cn/problem/CF1970B2)
------------
简单构造和模拟。
思路：根据题意可知一列只能放 $1$ 个房子，因此我们从左向右开始进行构造，因为 $a_1=0$ 因此我们将第一个房屋放在 $(1,1)$ 便于进行后面的处理，考虑接下来的 $j$ 和 $a_j$，如果 $a_j-j+1$ 刚好等于 $0$ ，说明此房屋和 $1$ 号房屋在同一行时，刚好能走到 $1$ 号房，那么我们就将该房屋放在第 $j$ 列，第 $1$ 行，并指向第一个房屋，如果 $a_j-j+1>0$，那么我们只需要将其向上移动即可，即将该房屋放在第 $j$ 列，第 $a_j-j+2$ 行，并让该房屋指向第一个房屋，如果 $a_j-j+1<0$，那么我们就找离他刚好这个距离的房屋即可，即放置在第 $j$ 列，第 $y_{i-a_i}$ 行（这里的 $y$ 指刚好距离所需放置房屋 $a_j$ 的目标房屋的行数）。
按这个操作从左到右构造下去一定能得到一个合法的方案，因为在 $a_i\le n$ 的情况下每个房子都能根据其距离到一个合法的位置，因此每个房子都能有一个合法的位置。
------------
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
void solve(){
int n;
scanf("%d",&n);
vector<int>a(n+10),x(n+10),y(n+10),ans(n+10);
rep(i,1,n)scanf("%d",&a[i]);
if(a[1]){cout<<"NO";return;}
x[1]=1,y[1]=1;
ans[1]=1;
rep(i,2,n){
if(!a[i]){x[i]=i,y[i]=1,ans[i]=i;continue;}
int now=a[i]-i+1;
if(now==0){x[i]=i,y[i]=1;ans[i]=1;continue;}
if(now>0){x[i]=i,y[i]=now+1;ans[i]=1;continue;}
else{x[i]=i,y[i]=y[-now+1],ans[i]=-now+1;continue;}
}
puts("YES");
rep(i,1,n)printf("%d %d\n",x[i],y[i]);
rep(i,1,n)printf("%d ",ans[i]);return;
}
int main()
{
solve();
return 0;
}
```