[13334번] 철로

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Priority_Queue

2. Map STL

3. 라인 스위핑

이 문제는 맵과 우선순위 큐로 해결할 수 있다.

우선 맵에는 어떤 방식으로 넣냐면, 인풋으로 a,b를 받을 때 무조건 a < b순이 아니기에

더 큰 값을 앞쪽에 넣어준다.

ex) mp[{10,1}] 이런식으로 큰값이 앞에 올 수 있도록 해준다.

이것의 의미는 각 사람의 집과 사무실중 더 먼것을 앞에 넣는다는 의미이다.

그렇게하면 어떤 사람의 검은색 줄 중 오른쪽 점->왼쪽 점 정렬 순으로 map에 차곡차곡 쌓이게 된다.

이제 맵을 한바퀴 돌며 라인 스위핑을 통해 정답을 구해보자.

hereE :: 현재 선의 끝점을 의미

hereS :: 현재 선의 시작점을 의미

hereC :: 끝점 - 시작점 즉, 길이

cnt :: 이러한 값이 몇개있는지? 즉, 시작점과 끝점이 같은 서로 다른 사람들이 있을 수 있다는 것(예제 3 참조)

이제 map에 의해 하나씩 뽑힐때 끝점의 값이 가장 작은 값부터 뽑히게 된다.

for(int i = 0 ; i < cnt; i ++)

pq.push(hereS);

현재 값을 우선순위 큐에 push해준다.(중복되는 값들 모두)

while (!pq.empty())

{

int top = pq.top();

if (hereE - d <= top)

break;

pq.pop();

}

두번째로 이제 hereE - d <= top 즉, 현재 끝점에서 철로길이를 뺀 값이 top 값(시작점 값)보다 작거나 같으면 

포함된다는 의미이므로 break를 해주고 그게 아니라면 포함되지 않는다는 의미이므로 pop을 해준다.

최종적으로 ans에 max값을 찾아내가면서 라인스위핑을 끝까지 진행한다.

좀더 자세한 그림을 원한다면 아래 링크를 찾아가보자.

http://blog.naver.com/occidere/221085858307

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
#include <functional>
 
using namespace std;
 
map<pair<int, int>, int> mp;
 
int main()
{
    int n;
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
 
        a > b ? mp[{a, b}]++ : mp[{b, a}]++;
    }
 
    int d;
    scanf("%d", &d);
 
    int ans = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
 
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        int hereE = it->first.first; // end
        int hereS = it->first.second; // start
        int hereC = hereE - hereS; // cost
        int cnt = it->second;
 
        for(int i = 0 ; i < cnt; i ++)
            pq.push(hereS);
 
        while (!pq.empty())
        {
            int top = pq.top();
            if (hereE - d <= top)
                break;
 
            pq.pop();
        }
 
        ans = max(ans, (int)pq.size());
    }
 
    printf("%d", ans);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>