Kyoto University Programming Contest 2017: A - Credits

,

http://kupc2017.contest.atcoder.jp/tasks/kupc2017_a

solution

整列して大きい方から貪欲に取る。$O(N \log N)$。

単位は多めに取っても大丈夫なので注意。 最近競プロを始めた友人氏がこの誤読で落としていた。

implementation

#!/usr/bin/env python3
n, k = map(int, input().split())
a = list(map(int, input().split()))
if sum(a) < k:
    print(-1)
else:
    a.sort(reverse=True)
    for i, a_i in enumerate(a):
        k -= a_i
        if k <= 0:
            break
    print(i + 1)