本文主要是介绍[CF746G]New Roads 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门QAQ

Preface

快要红名了，本来想搞篇题解水水分，结果在代码编写上卡住了。

码力不足QAQ

Analysis

首先都能看出来的是，题目中就是要求构造一棵 \(n\) 个点的树。

深度为 \(i\) 的结点有 \(a_i\) 个，且有 \(k\) 个叶子结点。

想一想就能发现，这样的一棵树叶子结点最少有 \(\sum\limits_{i=1}^{t-1} \max(a_i - a_{i+1},0)+a_t\) 个，

而最多有 \(\sum\limits_{i=1}^{t-1}(a_i-1)+a_t\) 个。

因此珂以直接将这俩数求出来，判断一下 \(k\) 是否满足条件即可。

考虑构造方法。

若 \(k\) 满足条件，\(k\) 肯定要比最小叶子结点数多一点，逐层枚举，将其分配到每一层。

下面是我卡住的地方。

根节点和深度为 \(1\) 的点肯定都要连边，用一个变量 \(now\) 统计当前连到了哪个点。

从高到低遍历每一层，求出这层的非叶子结点数量和叶子结点数量。

将下一层分配过来的多余的点全部连到最左边的结点上，其它的连到剩余的非叶子结点上。

这样口头描述相当难以理解，建议参考代码理解。

时间复杂度 \(O(N)\)。

Code

#include <bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
using namespace std;
const int maxn = 2e5 + 5;
int n,t,k,a[maxn],sum[maxn],cur[maxn];
vector<pair<int,int> > ans;
int main() {
	scanf("%d%d%d",&n,&t,&k);
	a[0] = 1;
	sum[0] = 1;
	for(int i = 1;i <= t;++ i)scanf("%d",&a[i]),sum[i] = sum[i - 1] + a[i];
	int tot = 0,cnt = 0;
	for(int i = 1;i < t;++ i)tot += cur[i] = max(a[i] - a[i + 1] , 0),cnt += a[i] - 1;
	tot += a[t];
	cnt += a[t];
	if(k < tot||k > cnt) {
		puts("-1");
		return 0;
	}
	k -= tot;//assigning
	for(int i = 1;i < t;++ i) {
		int c = a[i] - 1 - cur[i];
		if(k <= c) {
			cur[i] += k;
			k = 0;
			continue ;
		}
		else {
			cur[i] = a[i] - 1;
			k -= c;
			continue ;
		}
	}
	int now = 2;
	for(int i = 1;i <= a[1];++ i)ans.pb(mp(1 , now ++));
	for(int i = 1;i < t;++ i) {
		int l = now - a[i];
		tot = a[i + 1] - (a[i] - cur[i] - 1);
		for(;tot --;)ans.pb(mp(l , now ++));
		for(int k = l + 1;k <= l + a[i] - cur[i] - 1;++ k)ans.pb(mp(k , now ++));
	}
	printf("%d\n",n);
	for(auto u : ans) {
		printf("%d %d\n",u.fir,u.sec);
	}
	return 0;
}

完结撒花✿✿ヽ(°▽°)ノ✿

这篇关于[CF746G]New Roads 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！