C - Flush
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
今回は累積和を使う問題でした
入力例1ではAはソートすると以下のようになります
| i | 0 | 1 | 2 | 3 |
| A | 1 | 4 | 4 | 8 |
この時AiがBjより小さい場合はAiを、AiがBjより大きい場合はb-1を合計したものに+1すると答えがもとまります
例えばBj=2の時は、A0は1、A1,A2,A3のうちどれかを2個取れるようにします
また、毎回AiとBjを比較して合計していては時間がかかるので、累積和を求めておきます
| i | 0 | 1 | 2 | 3 |
| A | 1 | 4 | 4 | 8 |
| 累積和 | 1 | 5 | 9 | 17 |
これでbの大きさがAiを超えたところまでの累積和を取れば良いことになります
「bの大きさがAiを超えたところ」の計算はbisectを使いました
以下でACできました
from itertools import accumulate
import bisect
def i_map():
return map(int, input().split())
def i_list():
return list(map(int, input().split()))
n, q = i_map()
a = i_list()
a.sort()
tmp = list(accumulate(a))
tmp.insert(0, 0)
for i in range(q):
b = int(input())
idx = bisect.bisect_left(a, b)
num = 1 + tmp[idx] + (n - idx) * (b - 1)
if num > tmp[-1]:
print(-1)
else:
print(num)
コメント