1616: Taro's Shopping

太郎君の買い物

問題ページ①

問題ページ②

解き方

（※この解き方はあまり効率がよくありません。）

 はじめに、全商品の価格表を受け取ったらソートする。次に二分探索でソートした価格表から最大の金額ｍに最も近い価格を探し出してそのインデックスを取得する。

見つけたインデックスの商品（i: i > 0）とそのインデックスよりも前の商品（j: j >= 0 and i > j）の価格を足して最大の金額ｍ以下か調べていく。

二分探索で見つけたインデックスが確認し終わったらインデックスをー１してから、インデックスが１になるまでまた同じ確認作業を繰り返していく。

ソースコード（python）

コードは下のような感じです。制限時間以内に解くことはできますが、もっと効率よく解く方法はあります。

import bisect

while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    a = sorted(map(int, input().split()))
    index = bisect.bisect_left(a, m) - 1
    if index <= 0:
        print("NONE")
        continue
    ans = 0
    for i in range(index, 0, -1):
        for j in range(i-1, -1, -1):
            if a[i] + a[j] <= m:
                ans = max(ans, a[i] + a[j])
    if ans:
        print(ans)
    else:
        print("NONE")