题解：CF1970B2 Exact Neighbours (Medium)

0tAp · 2024-06-11 20:18:23 · 题解

题目链接：Exact Neighbours (Medium)

简单构造和模拟。

思路：根据题意可知一列只能放 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 的情况下每个房子都能根据其距离到一个合法的位置，因此每个房子都能有一个合法的位置。

代码如下：

#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;
}