AtCoder-ABC208 C - Fair Candy Distribution【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210705224035p:plain

AtCoder Beginner Contest208のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 208 - AtCoder

AtCoder Beginner Contest208 C - Fair Candy Distribution

問題文

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

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

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

制約

・1≤N≤2×10^5
・1≤K≤10^18
・1≤ai≤10^9
・ai は互いに異なる。
・入力は全て整数である。

解答例

n, k = map(int,input().split())

A = list(map(int, input().split()))

tmp = k // n

k = k % n

ans = [tmp for _ in range(n)]

order = []
for i in range(n):
    order.append([A[i], i])

order.sort()

for i in range(k):
    ans[order[i][1]] += 1

for a in ans:
    print(a)