题目大意

给定 $n$ 个点和 $m$ 个两两不同的小于 $n$ 的正整数 $c_1, \dots, c_m$，构造一个边数最少的有向图 $G$，使得 $G$ 没有自环，重边和双向边，且 $\forall 1 \le i \le m$，存在某个顶点，它的出度为 $c_i$ 或入度为 $c_i$。

题解

首先对 $c_i$ 进行桶排序，于是可以不妨设 $c_i$ 严格单调递增。

将每个顶点 $i$ 拆成两个点 $i^{+}$ 和 $i^{-}$，一个表示入边，一个表示出边，比如 $1$ 向 $2$ 连边就变成了 $1^-$ 和 $2^+$ 连边。不难发现得到的新图为无向二分图。

不妨先不考虑自环重边双向边的条件，则问题转化为：对一个无向二分图 $G=X+Y$，求 $|E(G)|_{\min}$ 使得存在 $m$ 个点度分别为 $c_1, c_2, \dots, c_m$。

实际上，我们考查度为 $c_{m-i+1}, \dots, c_{m-1}, c_m$ 的点，设其中有 $a$ 个点在 $X$ 内，$b$ 个点在 $Y$ 内，则 $a+b=i$。那么 $E(G)$ 包含这些点连出的所有边的并，而这个边数 $\ge \sum\limits_{k=m-i+1}^m c_k - ab$（总的减去重复算的）$\ge \sum\limits_{k=m-i+1}^m c_k - \left\lfloor\dfrac{i^2}{4}\right\rfloor$，因此我们得到了 $|E(G)|$ 的一个下界：

$$\max_{1 \le i \le m}\{\sum_{k=m-i+1}^m c_k - \left\lfloor\dfrac{i^2}{4}\right\rfloor\}$$

下面我们构造一个取得到这么多条边的例子。记 $X = \{u_1, \dots, u_n\}, Y=\{v_1,\dots, v_n\}$。设上式在 $i=t$ 时取到最大值，如果在多处取到最大就取 $t$ 最小的那个。记 $a = \left\lceil\dfrac{t}{2}\right\rceil, b = \left\lfloor\dfrac{t}{2}\right\rfloor$。

我们选定 $X$ 中的 $a$ 个点，让其中的点度分别为 $c_m, c_{m-2},\dots, c_{m-2(a-1)}$，且选定 $Y$ 中的 $b$ 个点，让其中的点度分别为 $c_{m-1}, c_{m-3}, \dots, c_{m-(2b-1)}$。不妨设这些点为 $u_1, \dots,u_a, v_1,\dots,v_b$。

我们的构造方式是：$\forall\ 1\le j\le a$，$u_j$ 与 $v_1, v_2, \dots, v_{c_{m-2j+2}}$ 连边；$\forall\ 1 \le k \le b$，$v_k$ 与 $u_1, u_2, \dots, u_{c_{m-2k+1}}$ 连边。

因为 $i=t$ 时上式取到最大值，所以 $c_{m-t} \le \left\lceil\dfrac{t}{2}\right\rceil$（$i=t$ 时与 $i=t+1$ 时两式比较），$c_{m-t+1} \ge \left\lceil\dfrac{t+1}{2}\right\rceil$（$i=t$ 时与 $i=t-1$ 时比较并结合 $t$ 的最小性）。我们又注意到在这样的构造下，度为 $1, 2, \dots, \left\lceil\dfrac{t}{2}\right\rceil$ 的点是必然存在的，因此这样的构造满足要求，同时我们发现当 $(u_1, u_2, \dots, u_n)=(1, 2, \dots, n)$，$(v_1, v_2. \dots, v_n) = (n, n - 1, \dots, 1)$ 时，这种构造可以直接搞定条件中的“没有自环重边双向边”。事实上，注意到不存在 $1 \le p \le q \le n$，使得 $p^+$ 与 $q^-$ 和 $p^-$ 与 $q^+$ 均连边。

在具体实现时我们并不需要先求出 $t$，直接按照这样的构造方式从大到小枚举，同时小端不断右移直至两端汇合即可，所以如果直接猜出了构造方式的话这题拿到 $100$ pts 也不需要最开始的论证，只不过在数学上缺少了严谨证明。

over，$o=0$ 时时间复杂度为 $\mathcal O(n^2)$，$opt=1$ 时时间复杂度为 $\mathcal O(m)$。