POJ-2566 : Bound Found
問題概要
長さN(<10^5)の数列が与えられる。長さ正の区間和で、絶対値がtに最も近いものを求める問題。
解法
しゃくとり法でやる。累積和をソートしておくと、http://d.hatena.ne.jp/komiyam/20120802/1343894601 でのfをf( [l,r) ) = accum[r] - accum[l] (ソート後)がt以上、とできるのでよい。
長さN(<10^5)の数列が与えられる。長さ正の区間和で、絶対値がtに最も近いものを求める問題。
しゃくとり法でやる。累積和をソートしておくと、http://d.hatena.ne.jp/komiyam/20120802/1343894601 でのfをf( [l,r) ) = accum[r] - accum[l] (ソート後)がt以上、とできるのでよい。