分数: 500 点
问题陈述
正在进行选举 N 候选人编号 1, 2, \ldots, N。有 K 选票,其中部分选票已统计完毕。
到目前为止,候选人 i 已收到 A_i 投票。
所有选票清点完毕后,候选人 i (1 \leq i \leq N) 当选当且仅当获得选票多于他们的候选人人数少于 M。 可能会有多名候选人当选。
对于每个候选人,从剩余选票中找到他们需要的最少额外票数,以保证他们的胜利,无论其他候选人如何获得选票。
正式地,为每个问题解决以下问题 i = 1,2,\ldots,N.
判断是否存在非负整数 X 不超过 K - \displaystyle{\sum_{i=1}^{N}} A_i 满足以下条件。 如果存在,找到该整数的最小可能值。
- 如果候选人 i 收到 X 追加票数,然后候选人 i 将始终被选中。
约束
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{12}
- 0 \leq A_i \leq 10^{12}
- \displaystyle{\sum_{i=1}^{N} A_i} \leq K
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M K A_1 A_2 \ldots A_N
输出
让 C_i 获得最少追加票数候选人 i 需要从剩余选票中保证自己的胜利,无论其他候选人如何获得选票。打印 C_1, C_2, \ldots, C_N 以空格分隔。
如果候选人 i 已经锁定胜局,那就让 C_i = 0。如果候选人 i 无论如何都无法确保胜利,那就让 C_i = -1.
示例输入 1
5 2 16 3 1 4 1 5
示例输出 1
2 -1 1 -1 0
14 目前已计票,并且 2 票数已剩。
的 C 输出为 (2, -1, 1, -1, 0)。 例如:
- 候选人 1 可以通过获得 2 更多票数,虽然不是通过获得 1 更多投票。 因此, C_1 = 2.
- 候选人 2 永远不能(即使他们获得 2 更多选票)确保了他们的胜利,所以 C_2 = -1.
示例输入 2
12 1 570 81 62 17 5 5 86 15 7 79 26 6 28
示例输出 2
79 89 111 117 117 74 112 116 80 107 117 106