牛客小白月赛55 E(构造)

E. 至至子的长链部分 (构造)

https://ac.nowcoder.com/acm/contest/38630/E

思路:

• 首先, $h$ 最大的节点必然是根节点, 并且只存在一个根节点
• 然后, 若要构成一棵合法的树, 长度 $0 - h_{max}$ 都必须出现, 比如: 0, 1, 2, 3, 4, 5;
• 最后, 长度 $h$ 的节点数要大于等于长度 $h + 1$ 的节点数(若小于, 某个 $h + 1$ 的节点没有对应的子节点, 根本无法满足 $h + 1$)

构造时:

我们把所有的 0 一个一个接到对应的 1 上, 0可能会多出来, 多出来的随便接即可

按照该顺序全部构造一遍一定能够构造出结果

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;

    map<int, vector<int>> mp;
    int mx = -1;
    for (int i = 1; i <= n; i++)
    {
        int h;
        cin >> h;

        mx = max(mx, h);

        mp[h].emplace_back(i);
    }

    // has two or more root node
    if (mp[mx].size() > 1)
    {
        cout << -1 << endl;
        return ;
    }

    // check
    for (int i = 0; i < mx; i++)
    {
        if (mp[i].size() < mp[i + 1].size())
        {
            cout << -1 << endl;
            return ;
        }
    }

    cout << mp[mx].front() << endl;
    for (int i = 0; i < mx; i++)
    {
        for (int j = 0; j < mp[i].size(); j++)
        {
            cout << mp[i][j] << ' ' << mp[i + 1][min(j, (int)mp[i + 1].size() - 1)] << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}