蟻本 巨大ナップサック p149 lower_bound

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)することで目的の値が得られる
  • これにより、重さピッタリで価値最大のものでも見つけられる