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;
}