演習課題「しゃくとり法の応用」
整数n,kと昇順にソートされた長さnの配列aが与えられます。
各i=0,1,...,n-1について、aに含まれる、値がa[i]+k以下の要素数を改行区切りで出力してください。
入力を受け取るコードがすでに用意されているので、コードを書き足してプログラムを完成させてください。
期待する出力値
3
4
5
5
5
＃09:区間の長さ
このチャプターでは、レベルアップ問題集「累積和メニュー」の「区間の長さ 4」の問題を解いてみます。
半開区間[l,r)(l以上r未満の区間)の長さはl,l+1,...,r-1の個数に等しく、r-lになります。
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
# 現在の右端を表す変数r,現在の総和を表す変数sum_value,答えを表す変数lengthを0で初期化
r, sum_value, length = 0, 0, 0
# 左端lを0からn-1まで繰り返す
for l in range(n):
# rがnより小さく、sum_valueにa[r]を加えてもkを超えない間
while r < n and sum_value+a[r] <= k:
# sum_valueにa[r]を加えて右端rを1ずつ増やす
sum_value += a[r]
r += 1
# もしr-lがlengthよりも大きければ
if r-l > length:
# lengthをr-lで更新
length = r - l
# もしlがrと同じなら
if l == r:
# rを1増やす
r += 1
# そうでなければ
else:
# sum_valueからa[l]を引く
sum_value -= a[l]
# lengthを出力
print(length)
5 3
8 1 1 1 3