Codeforces Round #583 (Div. 1 + Div. 2) E. Petya and Construction Set（树上构造）

题目链接


思路：先构造奇数点，其他奇数点在它的长度小于当前链的长度，那么就构造在i+len-1位置的分支上，否则就构造在链尾。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+1;
vector<pair<int,int>>v[maxn<<2];
pair<int,int>a[maxn];
int n;
bool cmp(const pair<int,int>&a,const pair<int,int>&b)
{
	return a.second>b.second;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i].second),a[i].first=2*i-1;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;++i) v[i].push_back(a[i]);
	int r=n;
	for(int i=1;i<=n;++i)
	{
		int size=v[i][0].first,len=v[i][0].second;
		if(i+len<=r) v[i+len-1].push_back({size+1,1});
		else v[++r].push_back({size+1,1});
	}
	for(int i=1;i<=r;++i)
	{
		if(i!=1) printf("%d %d\n",v[i-1][0].first,v[i][0].first);
		for(int j=1;j<v[i].size();++j) printf("%d %d\n",v[i][0].first,v[i][j].first); 
	}
}