ABC334 D - Reindeer and Sleigh

atcoder.jp

問題

• ソリがN台あるよ
• それぞれのソリを引くために必要なトナカイが、ソリ毎によって違ったりするよ
• 以下のクエリに答えてね
  • トナカイがX匹居たら、最大何台のソリ引ける？

成約

• $ 1 \leq N,Q \leq 2 \times 10^{5}$
• $ 1 \leq R_{i} \leq 10^{9}$
• $ 1 \leq X \leq 2 \times 10^{14}$

思考

• ソリの番号は気にしなくて良さそう
  • ソートして良いね
  • 必要なトナカイの数が少ない軽いソリから使いたいね
• ソリを引くために必要なトナカイの数を累積和で取って、にぶたんで$log(N)$で引けるので、$10^{5}$のクエリ処理できそうね
• 正直Cより簡単だった説ある…

コード

from bisect import bisect_right
from itertools import accumulate

N,Q = map(int,input().split())
R_L = list(map(int, input().split()))

R_L.sort()
accum_L = [0] + list(accumulate(R_L))

for _ in range(Q):
    X = int(input())
    print(bisect_right(accum_L, X)-1)