POJ 3061: Subsequence

Link：Subsequence

Problem: Find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S. (10 < N < 100000)

Solution 1(Not So Good): First preproccess the sum[i] stand for a[1] + a[2] + ... + a[i], then we can enum the starting point and use binary search to determine the ending point. This method cost O(n * log n) time.

Solution 2(Good): Using a algorithm called two pointer to solve this problem. I will try to describe this method.

i and j are our pointers, at first step i and j point to the first element of the sequence, tmp stand for the sum of the elements between pointer i and pointer j (0 <= i, j < N).

If tmp less than S: pointer i++; Else j-- until tmp less than S. At the same time, update the value of the answer.

This method cost O(n) time. Because i has been increasing, and j has bee decreasing. So the time complexity is O(n).

See the code bellow:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 100010;

int a[maxn], s, n, test;

int main() {
    scanf("%d", &test);
    for (int cas = 1; cas <= test; cas++) {
        scanf("%d %d", &n, &s);
        int ans = maxn, tmp = 0, j = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            tmp += a[i];
            if (tmp < s) {
                j = i;
            }
            while (tmp >= s) {
                if (i - j + 1 < ans)
                    ans = i - j + 1;
                tmp -= a[j];
                j++;
            }
        }
        if (ans == maxn)
            puts("0");
        else
            printf("%d\n", ans);
    }
}