poj3061: 爬行法

poj3061.md

Poj 3061

題目

分析

使用爬行法可在 O(n) 解。細節參「培養與鍛鍊程式設計的邏輯腦」。

AC Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

ll data[100000];

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        int N, S;
        scanf("%d %d", &N, &S);

        for (int i = 0; i < N; i++)
            scanf("%lld", &data[i]);

        // 爬行法 [s, t)
        int s = 0;
        int t = 0;
        ll sum = 0;
        int ans = N + 1;

        for (;;) {
            while (t < N && sum < S) {
                sum = sum + data[t++];
            }

            if (sum < S)
                break;

            if (t - s < ans)
                ans = t - s;

            sum = sum - data[s++];
        }

        if (ans > N)
            printf("0\n");
        else
            printf("%d\n", ans);
    }

    return 0;
}