1214E Petya and Construction Set

傳送門：http://codeforces.com/problemset/problem/1214/E

題意：讓你構造一棵節點為2n的樹，滿足2i 到 2*i-1的距離為d[i]且d[i]<=n

思路：首先我們可以看出2 4 6 8 等等邊是沒有任何顯示的 隻有奇偶邊才有現在

應為最大的d[i]<=n 是以我們可以可以通過給d[i]排序，

建立一條長度為n的長鍊 全為偶數構成，添加奇數點，

若目前偶數節點于奇數節點的距離為n則可以添加到長鍊末端

否則在長鍊中能找到一節點，在這個節點後添加一個分支滿足d[i]

ACcode:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n,b[maxn];
struct node{int d,i;}a[maxn];
bool cmp(node a,node b){return a.d>b.d;}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)   scanf("%d",&a[i].d),a[i].i=i;
	sort(a+1,a+n+1,cmp);
	for(int i=2;i<=n;i++) printf("%d %d\n",a[i-1].i*2,a[i].i*2);
	for(int i=1;i<=n;i++) b[i]=a[i].i*2;
	int now=n;
	for(int i=1;i<=n;i++)
    {
        int dis=i+a[i].d;
        if(b[dis] == 0) b[dis] = 2*a[i].i-1;
        printf("%d %d\n",2*a[i].i-1,b[dis-1]);
    }
	return 0;
}