CF1214E-Petya and Construction Set(树上构造)

题目传送门

题意：首先给你一个n(1<=n<=1e5)，接着输入n个数，第 i 个数 $d_i(1&lt;=d_i&lt;=n)$di​(1<=di​<=n) 表示点

$i*2$i∗2 和点 $i*2-1$i∗2−1 之间的距离为 $d_i$di​ ，最后，请你构造出这棵树并输出。

思路：首先，我们知道我们知道点 $i$i 只和点 $i+1$i+1 有关，和其他点无关，然后，我们就可以来

构造这棵树了，一般构造树的方法是先构造出一条长链，然后在链上加点和分支就行了，此题

我们先对长度数组从大到小排序，然后构造出一条长度为n的长链，长链的第i个位置放$d_i$di​所连

接的两点其中一点，然后判断$i+d_i-1$i+di​−1是否等于当前链长度(因为$d_i$di​<=n，所以不可能大于)

如果等于，就让链长度+1，把另一个点接在后面，否则，就把另一点当成分支接在第$i+d_i-1$i+di​−1

个点后面。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;

int n,a[N];
vector<int>e[N];
struct node{
	int idx,id;
}d[N];

int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>d[i].idx;
		d[i].id=i;
	}
	sort(d+1,d+1+n,[](node x,node y){return x.idx>y.idx;});
	int tot=n;
	for(int i=1;i<=n;i++){
		a[i]=d[i].id*2-1;
		if(i+d[i].idx-1>=tot){
			a[++tot]=d[i].id*2;
		} else {
			e[i+d[i].idx-1].push_back(d[i].id*2);
		}
	}
	for(int i=1;i<tot;i++){
		cout<<a[i]<<" "<<a[i+1]<<endl;
		for(auto v:e[i]){
			cout<<a[i]<<" "<<v<<endl;
		}
	}
	return 0;	
}