1806번: 부분합

https://www.acmicpc.net/problem/1806


$O(n)$

j<i tot=a[j+1]+a[j+2]+...+a[i]
i를 증가시키며 tot>s이면 tot<=s일 때까지 j를 증가시킨다.
tot>s일 때 i-j의 최솟값을 구한다.

#include<cstdio>
int n, s, a[100001], r = 1e9;
int main() {
    scanf("%d%d", &n, &s);
    for (int i = 1, j = 0; i <= n; i++) {
        scanf("%d", a + i);
        a[i] += a[i - 1];
        for (; a[i] - a[j] > s; j++) if (r > i - j) r = i - j;
    }
    printf("%d", a[n] > s ? r : 0);
    return 0;
}