백준 10165번: 버스 노선 [C++]

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

문제

버스 노선

풀이

$a < b$인 노선을 정상 노선, 그렇지 않은 노선을 비정상 노선이라 합시다.

이때 정상 노선끼리 포함하는 경우, 비정상 노선끼리 포함하는 경우, 비정상 노선이 정상 노선을 포함하는 경우만 생각하면 됩니다.

$a > b$인 비정상 노선은 항상 $N - 1$와 $0$을 지나고 정상 노선은 이를 지나지 않으므로 정상 노선이 비정상 노선을 포함할 수는 없습니다.

정상 노선끼리의 포함

스위핑을 통해 해결할 수 있습니다. $a$를 기준으로 오름차순, 만약 같다면 $b$를 기준으로 내림차순 정렬합니다. 반복문을 통해 돌면서 $b$의 최댓값을 기록하고, 만약 현재 보고 있는 노선의 $b$가 최댓값보다 작다면 다른 노선에 포함됩니다.

비정상 노선이 정상 노선을 포함

비정상 노선 중 $a$의 최솟값, $b$의 최댓값을 각각 구합니다. 정상 노선은 $N - 1$과 $0$을 지나지 않으므로 정상 노선의 $a$가 최솟값보다 크거나, $b$가 최댓값보다 작다면 비정상 노선에 포함됨을 알 수 있습니다.

비정상 노선끼리의 포함

정상 노선끼리의 포함과 같은 방법으로 해결할 수 있습니다. 비정상 노선의 $a$에 $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
#include <bits/stdc++.h>
using namespace std;

struct Line {
    int a, b, number;

    bool operator<(const Line& l) {
        if (a != l.a)
            return a < l.a;
        return b > l.b;
    }
};

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

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

    vector<bool> canceled(M);

    vector<Line> normal, abnormal;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;

        if (a < b)
            normal.emplace_back(a, b, i);
        else
            abnormal.emplace_back(a, b, i);
    }

    sort(normal.begin(), normal.end());

    int maxB = -1;
    for (auto [a, b, i] : normal) {
        if (b <= maxB)
            canceled[i] = true;
        else
            maxB = max(maxB, b);
    }

    int minA = N;
    maxB = -1;
    for (auto [a, b, _] : abnormal) {
        minA = min(minA, a);
        maxB = max(maxB, b);
    }

    for (auto [a, b, i] : normal) {
        if (canceled[i])
            continue;

        if (minA <= a)
            canceled[i] = true;
        if (b <= maxB)
            canceled[i] = true;
    }

    for (auto& [a, _, __] : abnormal)
        a -= N;

    sort(abnormal.begin(), abnormal.end());
    maxB = -1;
    for (auto [a, b, i] : abnormal) {
        if (b <= maxB)
            canceled[i] = true;
        else
            maxB = max(maxB, b);
    }

    for (int i = 0; i < M; i++)
        if (not canceled[i])
            cout << i + 1 << ' ';
    

    return 0;
}

백준 10165번: 버스 노선 [C++]