Edit

【pythonでABC208を解説】C - Fair Candy Distribution

問題概要

問題ページ

C - Fair Candy Distribution
C - Fair Candy Distribution

問題ページへ移動する

問題文

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

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

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

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

制約

  • \(1 \leq N \leq 2 \times 10^5\)
  • \(1 \leq K \leq 10^{18}\)
  • \(1 \leq a_i \leq 10^9\)
  • \(a_i\) は互いに異なる。
  • 入力は全て整数である。

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    dv, md = divmod(k, n)
    for i in range(n):
        a[i] = [a[i], dv, i]
    a.sort()
    for i in range(md):
        a[i][1] += 1
    a.sort(key=lambda x: x[2])
    for i in range(n):
        print(a[i][1])


if __name__ == '__main__':
    solve()

-Edit