公平的分享 (Fair Share, CF1634E)

1.5s 256MB

给你\(m(1\leq m\leq 10^5)\)个数组, 第\(i\)个数组\(a_i\)元素个数为\(n_i(2\leq n_i\leq 2\times 10^5,\sum\limits_{i=1}^{m}n_i\leq 2\times 10^5)\), \(n_i\)为偶数. 数组\(a_i\)的所有元素都是\([1,10^9]\)的整数. 一开始你有两个空的可重集\(L\)和\(R\). 对于每个数组\(a_i\), 你需要把\(a_i\)中的一半元素放入\(L\)中, 另一半放入\(R\)中. 你希望将\(m\)个数组分配完后能使得\(L=R\). 如果可能做到, 输出\(YES\)并给出构造, 否则输出\(NO\).

[分析]

首先, 如果有某个数字在所有\(a_i\)中出现的总次数为奇数, 那么答案一定是\(NO\). 以下考虑每个数出现的次数为偶数的情况. 将在所有\(a_i\)中出现的元素离散化以后(设在所有\(a_i\)中出现过的不同元素个数为\(n\)), 则我们得到一个\(m\times n\)的数表\(X\), 其中\(X_{ij}\)表示\(j\)在\(a_i\)中出现的次数. 于是每行每列的和均为偶数.

我们将每一行当作一个点, 每一列也当作一个点, \(X_{ij}\)表示行点\(i\)和列点\(j\)的边的个数. 于是我们得到一个二分图. 由于每个点的度数都是偶数, 因此图中存在欧拉路径. 于是我们可以将图中所有点定向, 使得每个点的出度和入度相同. 我们令由行点指向列点的边对应的数存入集合\(L\), 由列点指向行点的边对应的数存入集合\(R\), 则这样的构造满足要求.

时间复杂度为\(O(m+n+\sum\limits_{i=1}^{m}n_i)\)(如果使用\(unordered\_map\)进行离散化)(\(n\)是所有\(a_i\)中出现过的不同元素个数).