[c++] 백준 10165 버스 노선

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

10165번: 버스 노선

원이 나오는 문제이다.

'원이 나오면 일단 원을 끊어주자'라는 생각을 하게 되는데, 어떻게 끊을지가 관건이다.

0에서 끊어준다고 가정했을 때, 5번 노선이 문제가 되는데, 이것을 어떻게 할지 생각해 봤다.

5번 노선을 두 개로 만들어버리자.

0에서 오른쪽 기준으로는 [ -1, 4 ]

0에서 왼쪽 기준으로는 [ 9, 14 ]

이를 일반화하면, 정류소 개수가 n이고, [ a, b ]의 구간을 입력받았을 때,

[ a-n, b ], [a, b+n ] 이다.

그리고 0을 지나는 노선의 기준은 a > b 인 경우에 0을 지날 수 있다.

 

이렇게 원을 끊는 작업이 끝나면 스위핑을 통해, 노선들의 포함 관계를 판단해 줄 것이다.

이런 버스 노선이 있다 하자.

이 버스 노선을 시작점을 기준으로 정렬하자.

이때 노선의 종점들과의 관계를 보자.

빨간 노선 다음에는 주황 노선이 증가한다.

주황 노선 다음에는 노란 노선이 감소한다.

노란 노선 다음에는 초록 노선이 증가한다.

.

.

.

이 증감 관계를 생각해 보면 포함 관계를 찾을 수 있다.

예를 들어 1번 노선이 2번 을 포함하려면,

1번 시작점이 2번 시작점보다는 같거나 작아야 하고,

1번 종점이 2번 종점보다는 같거나 커야 한다.

 

위의 그림에서 노선들이 정렬되어 있으므로, 시작점은 차례로 단조 증가할 것이다.

탐색을 차례로 하면서 탐색할 종점과 탐색한 구간의 종점의 최댓값과의 증감을 조사하면,

포함 관계를 알 수 있다.

 

※주의사항

정렬할 때, 시작점이 같을 때 종점은 내림차순으로 정렬해야 한다.

오름차순으로 정렬하게 되면, 탐색 과정에 포함 관계를 놓치게 된다.

예를 들어 1번 노선과 2번 노선이 시작점이 같고, 1번 노선의 종점이 더 작다고 하자.

"( 1번 종점 < 2번 종점 ) 이므로 2번 종점은 포함 관계가 되지 않는다"라고만 판단이 되고,

1번 노선이 2번 노선에 포함됨을 놓치게 된다.

#include<bits/stdc++.h>
using namespace std;
#define F first.first
#define S first.second
#define station second
#define piii pair<pair<int,int>,int>
vector<piii> bus;
bool ans[500500];
bool cmp(piii a, piii b){
    if(a.F == b.F)
        return a.S > b.S;
    return a.F < b.F;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m; cin>>n>>m;
    for(int i=1; i<=m; i++){
        int a,b; cin>>a>>b;
        if(a>b){
            int l = n-a+b;
            bus.push_back({{a-n,b},i});
            bus.push_back({{a,b+n},i});
        }
        else
            bus.push_back({{a,b},i});
    }
    sort(bus.begin(),bus.end(),cmp);
    int M = bus[0].S;
    ans[bus[0].station] = 1;
    for(int i=1; i<bus.size(); i++){
        if(M < bus[i].S){
            M = bus[i].S;
            ans[bus[i].station] = 1;
        }
    }
    for(int i=1; i<=m; i++)
        if(ans[i])
            cout << i << ' ';
    return 0;
}