← 返回题目列表

AtCoder · abc373_e

H. 如何赢得选举

中文机器翻译题面 查看原题

分数: 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