どん底から這い上がるまでの記録

どん底から這い上がりたいけど這い上がれない人がいろいろ書くブログ(主にプログラミング)

1616: Taro's Shopping

太郎君の買い物

問題ページ①

問題ページ②

解き方

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

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

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

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

ソースコード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")