#UVa:1121-Subsequence

找出最短長度的數列可以比指定的數 S 大。

利用記住連續數列的最前端和最後端,慢慢從後面增長。如果總和超過了指定數 S ,則從最前端縮回來,直到數列總和比 S 小為止。

P.S. 記得處理總和沒辦法超過 S 的狀況。

C++(0.020)

/*******************************************************/
/* UVa 1121 Subsequence                                */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/16                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

int main(){
  int N, S;
  while(scanf("%d%d", &N, &S) != EOF){
    vector<int> sequence;
    for(int i = 0 ; i < N ; ++i){
      int number;
      scanf("%d", &number);
      sequence.push_back(number);
    }

    int sum = 0, minLength = N+1, front = 0;
    for(int i = 0 ; i < N ; ++i ){
      sum += sequence[i];

      while(sum >= S){
        minLength = min(minLength, i - front + 1);
        sum -= sequence[front];
        ++front;
      }
    }

    printf("%d\n", (minLength == N+1)? 0 : minLength);
  } 
  return 0;
}

沒有迴響

本文還沒有迴響,快來搶頭香!

發表迴響