AT_abc208_c [ABC208C] Fair Candy Distribution

题目描述

高桥王国有 $N$ 名国民。每位国民都有一个国民编号，第 $i$ 位国民的编号为 $a_i$。这里，$a_i$ 互不相同。

高桥君手上有 $K$ 个糖果。他决定按照以下规则分发糖果，直到糖果分完为止：

• 如果手上的糖果数量不少于 $N$，则每人分发 $1$ 个糖果。
• 否则，设此时高桥君手上的糖果数量为 $K'$，则从国民编号最小的 $K'$ 个人中，每人分发 $1$ 个糖果。更严格地说，从 $a_i$ 值较小的 $K'$ 个人中选出，每人分发 $1$ 个糖果。

请问，当所有糖果分发完毕后，第 $i$ 位国民最终获得了多少个糖果？

输入格式

输入以如下格式从标准输入读入。

$N$ $K$ $a_1$ $a_2$ $\ldots$ $a_N$

输出格式

输出 $N$ 行。第 $i$ 行输出第 $i$ 位国民获得的糖果数量。

输入输出样例 #1

输入 #1

2 7
1 8

输出 #1

4
3

输入输出样例 #2

输入 #2

1 3
33

输出 #2

3

输入输出样例 #3

输入 #3

7 1000000000000
99 8 2 4 43 5 3

输出 #3

142857142857
142857142857
142857142858
142857142857
142857142857
142857142857
142857142857

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10^{18}$
• $1 \leq a_i \leq 10^9$
• $a_i$ 互不相同。
• 输入均为整数。

样例解释 1

高桥君按照如下步骤分发糖果：

• 每人分发 $1$ 个糖果后，手上剩余 $5$ 个糖果。
• 每人再分发 $1$ 个糖果后，手上剩余 $3$ 个糖果。
• 每人再分发 $1$ 个糖果后，手上剩余 $1$ 个糖果。
• 给编号最小的第 $1$ 位国民分发 $1$ 个糖果后，糖果分完。 最终，第 $1$ 位国民获得 $4$ 个糖果，第 $2$ 位国民获得 $3$ 个糖果。

样例解释 2

由于只有 $1$ 位国民，高桥君会把所有糖果都分给第 $1$ 位国民。

由 ChatGPT 4.1 翻译