CF1970B2 Exact Neighbours (Medium) 题解

FFTotoro · 2024-05-05 19:13:11 · 题解

点这里前往游记。

下文中所有下标从 0 开始；称一栋房子的“目标”为其主人周末会去哪栋房子做客；因为每一列恰好有一栋房子，所以从左到右建房子。

因为 a_0=0，所以对于第一栋房子的目标设为其本身即可。

对于后面的房子，可以考虑直接根据前面已经建好的房子进行建造。具体地，如果 a_i=0 那么随便建；如果 a_i\ge i 那么就将 0 号房子作为目标，去掉往左走到第 0 列的贡献，可以轻易地确定这栋房子要建在第几列（因为 a_i\le n\Rightarrow a_i-i<n 并且 0 号房子在第 0 行，直接将其建在第 a_i-i 列即可）；如果 a_i<i 那么直接找到前面和它距离 a_i 的列，然后跟那一列上的房子建在同一行上即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<int> a(n),r(n),l(n);
  for(auto &i:a)cin>>i;
  if(!a[0]){ // B2 的特殊性质
    cout<<"YES\n1 1"<<endl,r[0]=1;
    for(int i=1;i<n;i++){
      if(!a[i]){cout<<i+1<<" 1\n",r[i]=1,l[i]=i; continue;}
      int x=a[i]-i;
      if(x>=0)cout<<i+1<<' '<<(r[i]=x+1)<<endl;
      else cout<<i+1<<' '<<(r[i]=r[l[i]=i-a[i]])<<endl;
    } // 只需模拟上面的构造
    for(int i:l)cout<<i+1<<' ';
    cout<<endl;
  }
  return 0;
}