https://www.codechef.com/COOK89/problems/MINSUBAR
N個の配列Aがある。
この中の連続部分列で、総和がD以上となるもので最小の長さを答えよ。
前提知識
- 累積和
- 座標圧縮
- セグメントツリー(区間min)
解法
連続部分列の右側を全探索しよう。
Rを固定して[L,R]を考えるが、満たすべき条件は「L<RかつD≦sm[L..R]」を満たすLのうち最も大きいLが得られると嬉しい。
D≦sm[L..R]を累積和を使って言い換えよう。
D≦sm[R] - sm[L - 1]
sm[L - 1]≦sm[R] - D
より、「L<Rかつsm[L - 1]≦sm[R] - D」を満たすLのうち最も大きいLを求める。
これは区間maxのセグメントツリーを使おう。
予めsm[i]とsm[i] - Dで座圧を準備しておこう。
これでsm[R]-D以下の区間を取れる。
L<Rは順次更新していこうようにして対応できる。
これでLを求めつつ、答えを更新していく。
#define INF INT_MAX int N; int D, A[101010], sm[101010]; //--------------------------------------------------------------------------------------------------- int solve() { cin >> N >> D; rep(i, 0, N) cin >> A[i]; sm[0] = A[0]; rep(i, 1, N) sm[i] = sm[i - 1] + A[i]; SegTree<int> st; st.init(N * 2 + 10); Zaatsu z; rep(i, 0, N) z.add(sm[i]), z.add(sm[i] - D); z.add(0); z.build(); st.update(z[0], -1); int ans = INF; rep(i, 0, N) { int id = st.get(0, z[sm[i] - D] + 1); if (-1 <= id) ans = min(ans, i - id); st.update(z[sm[i]], i); } if (ans == INF) ans = -1; return ans; } //--------------------------------------------------------------------------------------------------- void _main() { int T; cin >> T; rep(t, 0, T) printf("%d\n", solve()); }