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;
}

1999번: 최대최소

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

$O(n^2+k)$

n항의 수열이 존재할 때 monotonous queue를 이용해서 연속된 b개 마다의 최댓값, 최솟값을 구할 수 있다.

1. 주어진 행렬에서 각 행마다 연속된 b개의 최댓값, 최솟값을 구한다.
2. 이 값들로 다시 행렬을 만들어 각 열마다 연속된 b개의 최댓값, 최솟값을 구한다.
마지막 값들로 행렬을 다시 만들어 보면 b*b 마다의 최댓값, 최솟값이 구해져 있다.

#include<cstdio>
#include<deque>
using namespace std;
int n, b, k, maxi[251][251], mini[251][251];
void f(deque<pair<int, int> > &dq, int x, int y) {
    while (!dq.empty() && dq.back().second < y) dq.pop_back();
    dq.push_back({ x,y });
    if (x - dq.front().first >= b) dq.pop_front();
}
int main() {
    scanf("%d%d%d", &n, &b, &k);
    for (int i = 1; i <= n; i++) {
        deque<pair<int, int> > dq1, dq2;
        for (int j = 1, x; j <= n; j++) {
            scanf("%d", &x);
            f(dq1, j, x);
            f(dq2, j, -x);
            if (j >= b) {
                maxi[i][j - b + 1] = dq1.front().second;
                mini[i][j - b + 1] = -dq2.front().second;
            }
        }
    }
    for (int i = 1; i <= n - b + 1; i++) {
        deque<pair<int, int> > dq1, dq2;
        for (int j = 1; j <= n; j++) {
            f(dq1, j, maxi[j][i]);
            f(dq2, j, -mini[j][i]);
            if (j >= b) {
                maxi[j - b + 1][i] = dq1.front().second;
                mini[j - b + 1][i] = -dq2.front().second;
            }
        }
    }
    for (int x, y; k--;) {
        scanf("%d%d", &x, &y);
        printf("%d\n", maxi[x][y] - mini[x][y]);
    }
    return 0;
}

2905번: 홍준이와 울타리

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

#include<stdio.h>
#include<deque>
using namespace std;
const int MAX_N = 1e6;
int b[MAX_N + 1], n, x, res;
deque<pair<int, int> > dq;
typedef long long ll;
ll tot;
int main() {
    scanf("%d %d", &n, &x);
    for (int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
        tot += b[i];
    }
    int s = 0, tmp;
    for (int i = 0; i<x; i++) {
        while (!dq.empty() && dq.back().second>b[i]) dq.pop_back();
        dq.push_back({ i, b[i] });
    }
    tmp = dq.front().second;
    for (int i = x; i <= n; i++) {
        while (!dq.empty() && dq.back().second>b[i]) dq.pop_back();
        dq.push_back({ i, b[i] });
        if (tmp != dq.front().second) {
            res += (i - s - 1) / x + 1;
            tot -= (ll)(i - s)*tmp;
            s = i;
            tmp = dq.front().second;
        }
        if (dq.front().first <= i - x) {
            int tp = dq.front().first;
            dq.pop_front();
            if (tmp != dq.front().second) {
                res += (tp - s) / x + 1;
                tot -= (ll)(tp - s + 1)*tmp;
                s = tp + 1;
                tmp = dq.front().second;
            }
        }
    }
    printf("%lld\n%d", tot, res);
    return 0;
}

2812번: 크게 만들기

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


$O(n)$

주어진 길이 n의 문자열을 str

구한 답을 a[1],a[2], ...,a[n-k] 이라고 하자.

잘 생각해보면

a[1]=max(str[b1]) (0<=b1<=k)

a[2]=max(str[b2]) (b1<b2<=k+1)

...

a[n-k]=max(str[bn-k]) (bn-k-1<bn-k<n)

간단하게 큐 자료구조를 이용하여 O(n)에 a[]를 구할 수 있다.

#include<stdio.h>
#include<queue>
using namespace std;
int n, k;
char str[500001];
deque<char> q;
void push(char x) {
    while (!q.empty() && q.back()<x) q.pop_back();
    q.push_back(x);
}
int main() {
    scanf("%d %d %s", &n, &k, str);
    for (int i = 0; i<k; i++) push(str[i]);
    for (int i = k; i<n; i++) {
        push(str[i]);
        printf("%c", q.front());
        q.pop_front();
    }
    return 0;
}