[백준] 13334 철로

문제 주소 : www.acmicpc.net/problem/13334

13334번: 철로

fast io 미적용

문제 확인

 

스위핑과 우선순위 큐를 활용하는 문제입니다.

 

풀이

 

입력받은 선들을 x기준으로 내림차순 정렬을 한 후 우선순위 큐에 y 값을 내림차순으로 넣어 비교합니다.

비교식은 ary[i].x + dist < que.top() => que.pop() 이며 이러한 동작으로 인해 현재 이 조건을 만족하게 된다면 다음 단계에서 의미 없는 값이 되기 때문에 버립니다.

x값이 내림차순으로 정렬되어 있기 때문에 현재 비교식을 만족하지 못한다면 x값이 더 작은 다음 식을 절때 만족할 수 없기 때문에 pop으로 버려도 무방하기 때문입니다

이러한 식으로 끝까지 탐색을 하면서 최대값을 찾습니다.

 

코드

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef struct node {
    int x, y;
    bool operator<(const node &b) const {
        return x > b.x;
    }
}node;
int main() {
    node ary[100000];
    int n, d, max = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x < y)
            ary[i] = { x, y };
        else
            ary[i] = { y, x };
    }
    scanf("%d", &d);
    sort(ary, ary + n);
    priority_queue<int, vector<int>, less<int>> que;
    for (int i = 0; i < n; i++) {
        que.push(ary[i].y);
        while (!que.empty() && ary[i].x + d < que.top())que.pop();
        max = que.size() > max ? que.size() : max;
    }
 
 
    printf("%d", max);
}