有2n个点,每个2*i和2*i-1的距离必须是Di(<=n),现在让你构造这个树。
因为Di小于等于n,所以先对Di从大到小排序,把左端点排成一排,然后右端点搞搞就行。
注意:如果右端点应该插到最后一个点上面,那就把它变成新的最有一个点(++n)。
1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0); 2 #include <cstdio>//sprintf islower isupper 3 #include <cstdlib>//malloc exit strcat itoa system("cls") 4 #include <iostream>//pair 5 #include <fstream>//freopen("C:\\Users\\13606\\Desktop\\草稿.txt","r",stdin); 6 #include <bitset> 7 //#include <map> 8 //#include<unordered_map> 9 #include <vector> 10 #include <stack> 11 #include <set> 12 #include <string.h>//strstr substr 13 #include <string> 14 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9; 15 #include <cmath> 16 #include <deque> 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less 18 #include <vector>//emplace_back 19 //#include <math.h> 20 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor 21 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare) 22 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation 23 #define fo(a,b,c) for(register int a=b;a<=c;++a) 24 #define fr(a,b,c) for(register int a=b;a>=c;--a) 25 #define mem(a,b) memset(a,b,sizeof(a)) 26 #define pr printf 27 #define sc scanf 28 #define ls rt<<1 29 #define rs rt<<1|1 30 typedef long long ll; 31 void swapp(int &a,int &b); 32 double fabss(double a); 33 int maxx(int a,int b); 34 int minn(int a,int b); 35 int Del_bit_1(int n); 36 int lowbit(int n); 37 int abss(int a); 38 //const long long INF=(1LL<<60); 39 const double E=2.718281828; 40 const double PI=acos(-1.0); 41 const int inf=(1<<30); 42 const double ESP=1e-9; 43 const int mod=(int)1e9+7; 44 const int N=(int)1e6+10; 45 46 struct node 47 { 48 int id,len; 49 friend bool operator<(node a,node b) 50 { 51 return a.len>b.len; 52 } 53 }edge[N]; 54 vector<vector<node> >v(N); 55 56 int main() 57 { 58 int n; 59 sc("%d",&n); 60 for(int i=1;i<=n;++i) 61 sc("%d",&edge[i].len),edge[i].id=i*2-1; 62 sort(edge+1,edge+1+n); 63 for(int i=1;i<=n;++i) 64 v[i].push_back(edge[i]); 65 int End=n; 66 for(int i=1;i<=n;++i) 67 { 68 node temp=v[i][0]; 69 if(temp.len+i<=End) 70 v[i+temp.len-1].push_back({temp.id+1,1}); 71 else 72 v[++End].push_back({temp.id+1,1}); 73 } 74 for(int i=1;i<=End;++i) 75 { 76 if(i!=1) 77 pr("%d %d\n",v[i-1][0].id,v[i][0].id); 78 int sz=v[i].size(); 79 for(int j=1;j<sz;++j) 80 pr("%d %d\n",v[i][0].id,v[i][j].id); 81 } 82 return 0; 83 } 84 85 /**************************************************************************************/ 86 87 int maxx(int a,int b) 88 { 89 return a>b?a:b; 90 } 91 92 void swapp(int &a,int &b) 93 { 94 a^=b^=a^=b; 95 } 96 97 int lowbit(int n) 98 { 99 return n&(-n); 100 } 101 102 int Del_bit_1(int n) 103 { 104 return n&(n-1); 105 } 106 107 int abss(int a) 108 { 109 return a>0?a:-a; 110 } 111 112 double fabss(double a) 113 { 114 return a>0?a:-a; 115 } 116 117 int minn(int a,int b) 118 { 119 return a<b?a:b; 120 }
原文:https://www.cnblogs.com/--HPY-7m/p/11466350.html