#2800. [ABC208C] Fair Candy Distribution

[ABC208C] Fair Candy Distribution

[ABC208C] Fair Candy Distribution

题面翻译

有N个公民和K块糖果。每个公民都有一个唯一的身份证号码aia_{i}。小高决定按以下方式分发糖果,直到他没有更多的糖果:

  • 当他有N块或更多糖果时,每个公民分发一块。
  • 否则,假设他现在有K'块糖果,他会将这些糖果分发给身份证号码最小的K'个公民,每人一块。

当所有糖果分发完毕后,第i个公民会得到多少块糖果?

输入从标准输入中给出,格式如下:

NN KK

a1a_{1} a2a_{2} ... aNa_{N}

输出N行。第i行应包含第i个公民收到的糖果数量。

数据范围:1N2×105,1K1018,1ai1091 \leq N \leq 2 \times 10^{5},1 \leq K \leq 10^{18},1 \leq a_{i} \leq 10^{9},所有aia_{i}互不相同,输入中的所有值都是整数

样例说明1

小高将按以下方式分发糖果:

  • 每人分发一块,剩下5块。
  • 每人分发一块,剩下3块。
  • 每人分发一块,剩下1块。
  • 将最后一块分发给第1个公民。

最终,第1个公民将收到4块糖果,第2个公民将收到3块糖果。

样例说明2

由于只有一个公民,小高将所有糖果都分发给这第1个公民。

题目描述

高橋王国には N N 人の国民がいます。 全ての国民には国民番号が割り振られており、 i i 人目の国民の国民番号は ai a_i です。ここで、ai a_i は互いに異なります。

高橋君は K K 個のお菓子を持っています。高橋君は次のルールに従って、持っているお菓子が無くなるまで国民にお菓子を配ることにしました。

  • 持っているお菓子が N N 個以上ある場合、全員に 1 1 個ずつお菓子を配る。
  • そうでない場合、その時点で高橋くんが持っているお菓子の個数を K K' として、国民番号が小さい方から K K' 人に 1 1 個ずつ配る。より厳密には、ai a_i の値が小さい方から K K' 人を選び、選んだ人に 1 1 個ずつお菓子を配る。

全てのお菓子を配り終えたとき、i i 人目の国民は何個のお菓子を持っていますか?

输入格式

入力は以下の形式で標準入力から与えられる。

N N K K a1 a_1 a2 a_2 \ldots aN a_N

输出格式

N N 行出力せよ。i i 行目には 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  N  2 × 105 1\ \leq\ N\ \leq\ 2\ \times\ 10^5
  • 1  K  1018 1\ \leq\ K\ \leq\ 10^{18}
  • 1  ai  109 1\ \leq\ a_i\ \leq\ 10^9
  • ai a_i は互いに異なる。
  • 入力は全て整数である。

Sample Explanation 1

高橋君はお菓子を次の手順で配ります。 - 全員に 1 1 個ずつお菓子を配り、高橋君の持っているお菓子は 5 5 個になる。 - 全員に 1 1 個ずつお菓子を配り、高橋君の持っているお菓子は 3 3 個になる。 - 全員に 1 1 個ずつお菓子を配り、高橋君の持っているお菓子は 1 1 個になる。 - 1 1 人目の国民に 1 1 個お菓子を配り、高橋君の持っているお菓子は無くなる。 最終的に 1 1 人目の国民は 4 4 個、2 2 人目の国民は 3 3 個のお菓子を手に入れることができます。

Sample Explanation 2

国民が 1 1 人しかいないので、高橋君は全てのお菓子を 1 1 人目の国民に配ることになります。

Statistics

Related

In following homework:

结构体排序