P12636 [UOI 2020] Array Reduction

5s 512M

给定一个包含 $n$ 个整数的数组 $a$。每次操作中，你可以选择一个位置 $i$（$1 \leq i \leq n$），将 $a_i$ 减少 $k$，同时将所有其他元素 $a_j$（$1 \leq j \leq n$ 且 $i \neq j$）增加 $t$。 求将数组中所有元素变为非正数（即小于或等于零）所需的最少操作次数。如果无法实现，则报告该情况。

第一行包含三个整数 $n$、$k$、$t$（$1 \leq n \leq 10^6$，$0 \leq k, t \leq 10^9$）——数组长度及操作参数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^{18} \leq a_i \leq 10^9$）——数组元素的初始值。

输出一个整数 $c$——将数组所有元素变为非正数所需的最少操作次数。如果无法实现，输出 $-1$。 如果可以实现，还需输出 $n$ 个整数 $cnt_i$（$1 \leq i \leq n$），表示对第 $i$ 个元素执行的操作次数。注意必须满足 $\sum\limits_{i=1}^n cnt_i = c$。

- （$3$ 分）$t = 0$； - （$5$ 分）$1 \leq n \leq 300$，$0 \leq |a_i| \leq 300$，$0 \leq t \leq 10^6$； - （$8$ 分）$1 \leq n \leq 3000$，$0 \leq |a_i| \leq 3000$，$0 \leq t \leq 10^6$； - （$9$ 分）$1 \leq n \leq 10^3$，$1 \leq a_i \leq 10^9$，$0 \leq t \leq 10^6$； - （$5$ 分）$1 \leq n \leq 10^4$，$1 \leq a_i \leq 10^9$； - （$13$ 分）$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^9$； - （$8$ 分）$1 \leq a_i \leq 10^9$； - （$9$ 分）$1 \leq n \leq 10^3$，$0 \leq t \leq 10^6$； - （$5$ 分）$1 \leq n \leq 10^4$； - （$14$ 分）$1 \leq n \leq 10^5$； - （$21$ 分）无额外限制。 翻译由 DeepSeek V3 完成