ZOJ 3123 Subsequence
問題
長さNの数列a[0],..,a[N]が与えられる。総和がSを超えるような連続する部分列の、最小の長さを求めよ。
解法
まず部分和sを計算する(s[i+1] = s[i] + a[i], s[0] = 0)。
するとa[i],...,a[j]の総和はs[j+1]-s[i]となるので、始点iを決めると、終点はS+s[i]の二分探索で求まる。
コード
int main(){ int T; cin>>T; while(T--){ int N,S; cin>>N>>S; vector<int> a(N); REP(i,N)cin>>a[i]; vector<int> sum(N+1); REP(i,N)sum[i+1] = sum[i]+a[i]; int ans = INF; REP(i,N){ int cond = S + sum[i]; vector<int>::iterator it = lower_bound(sum.begin(),sum.end(),cond); if(it != sum.end()){ ans = min(ans, (int)distance(sum.begin(),it) - i); } } if(ans == INF) ans = 0; cout<<ans<<endl; } return 0; }