题目链接

Subsequence POJ - 3061

思路

$$ 尺取法入门题 $$

时间复杂度

$$ O(N) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 10;
int a[MAXN];

int main() {
    int T;
    scanf("%d", &T);// don't forget &
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);// don't forget &
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);// don't forget &
        }
        int s = 1, t = 1, sum = 0;
        int res = n + 1;
        while (true) {
            while (t <= n && sum < m) {
                sum += a[t++];
            }
            if (sum < m) {
                break;
            }
            res = min(res, t - s);
            sum -= a[s++];
        }
        if (res == n + 1) {
            res = 0;
        }
        printf("%d\n", res);
    }


    return 0;
}