if(sw <= W){ ll tv = (lower_bound(ps,ps+m,pll(W-sw,INF))-1)->second; res = max(res,sv+tv); }
- 後半、こういう箇所がありますよね
- -1を引くとどうなるか。イテレータの1つ手前を指す
- 「W-swピッタリの重さがあったら、-1しちゃダメなのでは?」と疑問を持つ
- それは勘違いで、INFがポイント
- 重さピッタリのものがlower_boundの範囲内で見つかったとしても、第二引数(pair.second)がINFなので、その値は絶対に見つからない
- 例:重さ120を探した時、pair(120, INF)でlower_boundするので、見つかる値は例えば(121, 何らかの価値)などであり、そこから1つイテレータを戻す(-1)することで目的の値が得られる
- これにより、重さピッタリで価値最大のものでも見つけられる