CF746G New Roads 题解

题目链接：New Roads

题意：

在Berland有 \(n\) 个城市，每一座城市都有一个单独的编号——在 \(1\) 到 \(n\) 范围内的一个整数，首都的编号是 \(1\)。现在，在Berland有一个极其严峻的问题：城市之间没有道路相连。

为了使得每个城市之间都有路相连，要在城市之间建造 \(n-1\) 条路。

在建造计划中一共有 \(t\) 个整数 \(a_1,a_2,\cdots,a_t\) ，其中 \(t\) 等于首都与离首都最远的城市之间的距离。\(a_i\) 表示一共有 \(a_i\) 座城市与首都之间的距离是 \(i\)。两个城市之间的距离等于从一座城市到另一座城市所经过的道路的数量。

而且，除了首都以外一共会有 k 座城市仅与一条道路相连。这些城市是“死胡同”，它们没有经济吸引力。首都不算在内（即，即使只有一条道路与首都相连，首都也不算在“死胡同”里）。

你的任务是做出符合所有条件的计划，或是说明符合所有条件的计划是不存在的。

输入格式：

输入数据的第一行包括三个整数 \(n,t,k~(2 \le n \le 2\times10^5 , 1 \le t , k <n)\)，表示城市总数，首都与距离首都最远的城市之间的距离以及作为“死胡同”的城市个数。

第二行包括一个含有 \(t\) 个整数的数列 \(a_1,a_2,\cdots a_n~(1 \le a_i \le n)\)，表示与首都距离为 \(i\) 的城市有 \(a_i\) 个。输入数据保证数列里所有数的总和为 \(n-1\)。

输出格式：

如果不存在符合全部条件的方案，输出 \(-1\)。

否则，在第一行输出一个整数 \(n\)，表示城市个数。在接下来的 \(n-1\) 行中每一行包括两个整数，表示在这两个城市之间有道路相连。你可以以任意顺序输出。(注：此处任意顺序指道路顺序及每条道路所连接的的城市顺序均可以任意顺序输出)

如果有多组解，输出任意一组。记住首都的编号是 \(1\)。

方便期间，记根节点的深度为 \(1\) ，相应的所有的 \(a_i\) 后移一位。

可以想到去构造叶节点最少和最多的情况，可以发现样例2的情况如下（图来自参考文献1）

可以发现（下文中 \(\uparrow\) 表示两侧的最大值） \[ k_{\max} = a_t + \sum_{i=1}^{t-1}(a_i-1) \\ k_{\min} = a_t + \sum_{i=1}^{t-1}(a_i - a_{i+1}\uparrow 0) \] 除了第一层和最后一层，每层的节点数都在 \([(a_i - a_{i+1} \uparrow 0),~a_i-1]\) 内。

记 \(b_2,b_3,\cdots,b_{t-1}\) 为每一层要构造的点数，且 \(\sum_{i=2}^{t-1}b_i = k - a_t\) ，直接构造即可

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define pb push_back
#define N ((int)(2e5 + 15))

vector<pii> ans;
int n, t, k, a[N], b[N], sum[N];
int id(int x, int y) { return sum[x - 1] + y; }
int mn()
{
    int res = a[t];
    rep(i, 1, t - 1) if(a[i] > a[i + 1]) res += a[i] - a[i + 1];
    return res;
}
int mx()
{
    int res = a[t];
    rep(i, 1, t - 1) res += a[i] - 1;
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> t >> k; ++t; sum[1] = a[1] = 1;
    rep(i, 2, t) { cin >> a[i]; sum[i] = sum[i - 1] + a[i]; }
    if(k < mn() || k > mx()) { return cout << "-1\n", 0; }
    int num = k - a[t], tmp;
    rep(i, 2, t - 1) { b[i] = max(0ll, a[i] - a[i + 1]), num -= b[i]; }
    rep(i, 2, t - 1) { tmp = min(num, a[i] - 1 - b[i]); b[i] += tmp; num -= tmp; }
    rep(i, 1, t - 1)
    {
        int x = a[i] - b[i];
        rep(j, 1, x) ans.pb({id(i, j), id(i + 1, j)});
        rep(j, x + 1, a[i + 1]) ans.pb({id(i, x), id(i + 1, j)});
    }
    cout << n << '\n';
    for(auto i : ans) cout << i.first << ' ' << i.second << '\n';
    return 0;
}