6116번: Tower of Hay

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

풀이 링크: http://contest.usaco.org/TESTDATA/OPEN09.tower.htm

시간복잡도는 $O(n)$

#include<cstdio>
int n, a[100001], h, t, bar[100001], s[100001], r[100001];
int main() {
    scanf("%d", &n);
    for (int i = n; i; i--) scanf("%d", a + i);
    for (int i = 1; i <= n; i++) {
        a[i] += a[i - 1];
        while (h <= t && bar[h] <= a[i]) h++;
        while (bar[t] > 2 * a[i] - s[h - 1]) t--;
        bar[++t] = 2 * a[i] - s[h - 1];
        s[t] = a[i];
        r[t] = r[h - 1] + 1;
    }
    printf("%d", r[t]);
    return 0;
}