UVALive2678:Subsequence

题目大意

给定一个数组A和一个整数S。求数组A中，连续且之和不小于S的连续子序列长度最小值。

要求复杂度:Ο(n)

Solution

用变量L表示所选区间最左端下标，用变量R表示所选区间最右端下标，用变量sum表示所选区间的和。从左到右扫描一遍数组，如果sum比S小，则右移R，扩大所选区间，从而增大sum。通过不断的右移L达到遍历整个数组的目的。

Note

当解不存在时需要输出0。不知道为什么题目中并没有明确的指出这一点，但如果不加以考虑一定会WA。
数组中单个元素不超过int类型的表示范围，但子序列之和有可能超过，因此需要使用long long类型

AC-Code(C++)

Time:33ms

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 100000 + 10;

/*
 * 刘汝佳 训练指南 P48
 */


int A[maxn];

int main(int argc, const char * argv[]) {

//    freopen("input.txt", "r", stdin);


    int N,S;
    while(scanf("%d %d",&N,&S)==2){
        for(int i=0;i<N;i++){
            scanf("%d",A+i);
        }
        ll sum = 0; // long long is needed here!!!
        int R = 0;
        int L = 0;
        int ans = INF;
        while (L<N) {
            while(sum<S && R<N){
                sum += A[R++];
            }
            if(sum<S)
                break;
            ans = min(ans,R-L);
            sum -= A[L++];
        }
        // if solution doesn't exist, print 0 instead.
        ans = ans == INF ? 0 : ans;
        printf("%d
",ans);
    }

    return 0;
}