【Codeforces 1214E】Petya and Construction Set | Mrsrz's blog

构造

题目大意：

给你 $2n$ 个结点，要构造一棵树，边权为 $1$。

有 $n$ 个限制，第 $i$ 个限制是，编号为 $2i-1$ 和 $2i$ 的结点的距离必须为 $d_i$。

保证 $d_i\in[1,n]$。

要求输出一种符合条件的树。

题解：

构造题。

考虑按 $d_i$ 从大到小排序。

我们先预留一条链，前 $n$ 个位置留给编号为奇数的结点，后 $n$ 个位置留给编号为偶数的结点。

我们直接把奇数编号的结点按照 $d_i$ 的大小放入前 $n$ 个位置，大的放前面。然后依次考虑每个位置的限制。

设离当前这个位置最近的空着的留给编号为偶数的结点，离当前位置的距离为 $k$。

如果当前考虑的限制 $d_i=k$，则直接把它填到离当前位置距离为 $k$ 的那个空位上，然后对于下一个结点，离它最近的空位的距离显然还是 $k$。

否则，我们找一个已经放入结点的位置，作为待填结点的父亲，使得满足 $d_i$ 限制即可。此时，对于下一个结点，其 $k$ 比当前的 $k$ 小 $1$。

不难发现，这个算法执行的过程中，始终保证每个位置的 $d_i\leqslant k$，因此当 $d_i\neq k$ 时一定能找到一个符合条件的位置。所以构造方法正确。

时间复杂度 $O(n\log n)$ 或 $O(n)$。为了方便我直接使用了 sort 排序。

Code：

#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
const int N=2e5+6;
pair<int,int>d[N],out[N];
int n,lst,tot,dist,L[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>d[d[i].second=i].first;
    sort(d+1,d+n+1,greater<pair<int,int> >());
    for(int i=1;i<n;++i)
        out[++tot]=make_pair(d[i].second*2-1,d[i+1].second*2-1);
    for(int i=1;i<=n;++i)L[i]=d[i].second*2-1;
    lst=n;
    dist=n;
    for(int i=1;i<=n;++i){
        if(d[i].first==dist){
            out[++tot]=make_pair(L[lst],d[i].second*2);L[++lst]=d[i].second*2;
        }else{
            int pos=i+d[i].first-1;
            out[++tot]=make_pair(L[pos],d[i].second*2);
            --dist;
        }
    }
    for(int i=1;i<=tot;++i)
        cout<<out[i].first<<' '<<out[i].second<<'\n';
    return 0;
}