CF1666B Budget Distribution

在有限资源和众多约束下分配预算资金是一个难题。一个预算方案包含 $t$ 个主题，第 $i$ 个主题包含 $n_i$ 个项目。对于每个主题，已知最优的相对资金分配。第 $i$ 个主题的最优相对分配是一个实数列表 $p_{i,j}$，其中 $\sum\limits_{j=1}^{n_i}{p_{i,j}} = 1$。 我们用 $c_{i, j}$ 表示分配给第 $i$ 个主题的第 $j$ 个项目的资金数额；该主题的总资金为 $C_i = \sum\limits_{j=1}^{n_i}{c_{i,j}}$。第 $i$ 个主题的非最优性定义为 $\sum\limits_{j=1}^{n_i}\left|\frac{c_{i, j}}{C_i} - p_{i, j}\right|$。通俗地说，非最优性是所有项目实际分配比例与最优分配比例之差的总和。总方案的非最优性是所有 $t$ 个主题的非最优性之和。你的任务是最小化总方案的非最优性。 然而，目前可用的确切资金总额尚不确定。第 $i$ 个主题的第 $j$ 个项目已经被分配了 $\hat c_{i,j}$ 美元，这部分资金不能回收。此外，还有 $q$ 个可能的未分配额外资金 $x_k$。对于每一个 $x_k$，你需要计算在所有分配方式中最小可能的总非最优性。你不需要将整数金额分配给每个项目，任何实数金额都可以，但所有额外资金必须分配到所有项目上，并且要加上已经分配的 $\hat c_{i,j}$。形式化地，对于每个额外资金 $x_k$，你需要找到一种分配方式 $d_{i,j}$，使得 $d_{i, j} \ge 0$ 且 $\sum\limits_{i=1}^{t}\sum\limits_{j=1}^{n_i} d_{i,j} = x_k$，从而得到最终的预算分配 $c_{i,j} = \hat c_{i,j} + d_{i,j}$，并使总方案非最优性最小。

第一行包含两个整数 $t$（$1 \le t \le 5 \cdot 10^4$）和 $q$（$1 \le q \le 3 \cdot 10^5$）——预算中的主题数和可能的额外资金数。 接下来的 $t$ 行描述每个主题。每行以一个整数 $n_i$（$2 \le n_i \le 5$）开头，表示第 $i$ 个主题的项目数；接下来是 $n_i$ 个整数 $\hat c_{i, j}$（$0 \le \hat c_{i, j} \le 10^5$；对于任意 $i$，至少有一个 $\hat c_{i,j} > 0$），表示已经分配给第 $i$ 个主题第 $j$ 个项目的资金数额；再接下来是 $n_i$ 个整数 $p'_{i,j}$（$1 \le p'_{i,j} \le 1000$），它们确定 $p_{i,j}$ 的值，具体为 $p_{i, j} = {p'_{i, j}} \big/ {\sum\limits_{j=1}^{n_i}{p'_{i, j}}}$，满足 $\sum\limits_{j=1}^{n_i}{p_{i,j}} = 1$。 下一行包含 $q$ 个整数 $x_k$（$0 \le x_k \le 10^{12}$），表示第 $k$ 个可能的额外资金数额。

输出 $q$ 个实数，分别表示对应额外资金 $x_k$ 时的最小可能非最优性。每个答案的绝对误差或相对误差不超过 $10^{-6}$。

由 ChatGPT 4.1 翻译