Codeforces 746G New Roads

题目链接

https://codeforces.com/contest/746/problem/G

题目大意

告诉你一棵树有 N 个节点 , 其中 1 为树根 , 树有T 层，第 i 层节点个数为 a(i-1) , 叶子节点的个数为 K 

问你能否构造出树边使得这棵树满足以上条件

解题思路

思维 + 构造

很显然当本层的节点全都指向一个父节点时，叶子节点个数最多

当本层节点分散指向不同父节点时，叶子节点个数最少

那么叶子节点最多为 ma =  a[t] + (a[t - 1] - 1) + (a[t - 2] - 1) + ... + (a[1] - 1)

最少为 mi = a[t] + max(0 , a[t - 1] - a[t]) + ... + max(0 , a[1] - a[2])

所以当 K 不在 mi ~ ma 这个范围之内就一定无法构造，反之必然可以构造

当叶子节点个数等于 ma 时，代表每层的节点都指向上一层的同一父节点

那么当第 i 层其中一个节点指向另一个父节点节点后, ma的数量就会减少min(1,a[i-1]-1)

其中两个节点指向另外两个父节点后，ma的数量就会减 min(2 , a[i - 1] - 1)

于是当 ma > k 时，我们就可以按照上述操作不断减少 ma，直到 ma = k 时，再按照所有节点指向同一个父节点的方法构造即可

AC_Coder

#include<bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define fi first
#define se second
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N] , ma , mi;
vector<int>num[N];
vector<pair<int , int>>ans;
signed main()
{
    int n , t , k , cnt = 1;
    cin >> n >> t >> k;
    rep(i , 1 , t) cin >> a[i];
    
    ma = a[t] , mi = a[t];
    
    per(i , t - 1 , 1)
        ma +=  a[i] - 1 , mi +=  max(0LL , a[i] - a[i + 1]);
 
    if(k > ma || k < mi) return cout << -1 << '
' , 0;
    
    num[0].pb(1);
    rep(i , 1 , t)
    {
        int j = 0 ;
        num[i].pb(++ cnt);
        ans.pb(make_pair(num[i - 1][0] , cnt));
        a[i] -- ;
        while(a[i] && j < num[i - 1].size())
        {
            if(k < ma && j + 1 < num[i - 1].size()) 
            j ++ , ma -- ;
            ans.pb(make_pair(num[i - 1][j] , ++ cnt)) , num[i].pb(cnt); 
            a[i] -- ;
        }
    }
    cout << n << '
';
    for(auto i : ans) cout << i.fi << " " << i.se << '
';
    return 0;
}