백준 2821번: 컨베이어 벨트 [C++]

작성일 | In
플래티넘 I 플래티넘 I

문제

컨베이어 벨트

풀이

$j - 1$번째 차의 작업을 시작하고 나서 $j$번째 차의 작업을 시작하기까지의 시간을 $d$라 합시다. $d$에는 쉬는 시간 뿐 아니라 작업 시간도 포함되어 있음에 유의합시다.

$S_n = \sum_{k = 1}^n T_k$으로 정의하면 $d$는 모든 $i$에 대해 부등식 $d + S_{i - 1}F_j \ge S_iF_{j - 1}$을 만족해야 합니다.

이는 $j$번째 차의 작업의 시작 시간(좌변)이 $j - 1$번째 작업의 끝(우변) 이후여야 함을 뜻합니다.

해당 부등식을 변형하면 $d \ge S_iF_{j - 1} - S_{i - 1}F_j$입니다. 따라서 우변의 최댓값이 $d$의 최솟값이 됩니다.

정확히는 상근이의 작업시간까지도 포함해야 하므로 우변의 최댓값과 $T_1F_{j - 1}$중 최댓값이 $d$의 최솟값이 됩니다.

우변을 $F_j$로 묶으면 $F_j\left(S_i\dfrac{F_{j - 1}}{F_j} - S_{i - 1}\right)$ 이고 이는 변수가 $F_{j - 1} / F_j$, 기울기가 $S_i$, y 절편이 $-S_{i - 1}$인 직선에 $F_j$를 곱한 것으로 볼 수 있습니다.

따라서 볼록 껍질을 이용한 최적화를 사용하면 시간 복잡도 $\mathcal{O}(N + M\log N)$에 해결할 수 있습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(ignore) ((void)0)
#endif
using namespace std;

using ll = long long;
using ld = long double;

ll sum[101010];

struct Line {
    int idx;
    ll slope, yinter;
    ld start;
    Line(int _idx, ll _slope, ll _yinter)
        : idx(_idx), slope(_slope), yinter(_yinter), start(-INFINITY) {}

    ld getIntersection(const Line& l) {
        return (ld)(l.yinter - yinter) / (slope - l.slope);
    }
};

// Only supports inserting lines in strictly increasing slope order
struct LineContainer {
    vector<Line> lines;

    void push(Line l) {
        while (not lines.empty()) {
            Line back = lines.back();

            ASSERT(l.slope != back.slope);

            l.start = l.getIntersection(back);
            if (l.start <= back.start)
                lines.pop_back();
            else
                break;
        }

        lines.push_back(l);
    }

    // Returns idx of line
    int query(ld x) {
        return (upper_bound(lines.begin(), lines.end(), x,
                            [](ld v, const Line& l) { return v < l.start; }) -
                1)
            ->idx;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    LineContainer container;
    for (int i = 1; i <= N; i++) {
        cin >> sum[i];
        sum[i] += sum[i - 1];

        container.push(Line(i, sum[i], -sum[i - 1]));
    }

    int before, now;
    cin >> now;
    ll ans = 0;
    for (int i = 2; i <= M; i++) {
        swap(before, now);
        cin >> now;

        int idx = container.query((ld)before / now);
        ans += max(before * sum[1], sum[idx] * before - sum[idx - 1] * now);
    }
    ans += sum[N] * now;

    cout << ans;

    return 0;
}

백준 2821번: 컨베이어 벨트 [C++]