[BOJ-13334]철로

5달전에 풀려고 했다가 뭐지? 하고 그냥 틀린상태로 있던 문제였음..

일단 아무생각없이 코드를 작성했을 때는 으로 풀었었는데...

다시 문제 보고 풀어보려고 했을 때도 처음에 정렬하고 그저 하나씩 세어보지 뭐 하면서 생각했음...

입력 자료의 갯수가 (s[i], f[i]) s는 start, f는 finish 순서로.. 무조건 오름차순으로 바꾸고 시작점과 거리를 저장했다. 근데 지금다시생각해보니 그짓을 할 필요가 없다. 그냥 시작점, 도착점으로 집-회사 / 회사-집 상관없이 낮은 것을 시작점, 높은 것을 도착점으로 생각하면 된다. 

TLE(시간초과) 예상하고 제출했었다.

#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
#define din1(a) scanf("%d",&a)
#define din2(a,b) scanf("%d%d",&a,&b)
#define din3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define din4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define dout1(a) printf("%d",a)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define start first
#define length second
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
//struct point{
//    int start;
//    int length;
//    point(){}
//    point(int is, int il):start(is), length(il){}
//};
 
typedef vector<pii> vp;
 
int n;
vp input;
vp refine;
 
pii crop_data(int s, int l){
    pii ret; 
    ret.start = (s>l)?l:s;
    ret.length = (l-s>0)?l-s:s-l;
    return ret;
}
 
int main(){
    // input 
    din1(n);
    for(int i = 0 ; i < n ; i++){
        int h,o; din2(h,o);
        pii ret = crop_data(h,o);
        input.pb(ret);
    }
    int dist; din1(dist);
 
    for(int i = 0 ; i < n ; i++){
        if(input[i].length <= dist) refine.pb(input[i]);
    }
    // input end
 
    int ans = 0;
    int pivot_max;
    // operation
    sort(refine.begin(), refine.end());
    int size = refine.size();
    for(int i = 0 ; i < size ; i++){
        int here = refine[i].start + dist;
        pivot_max = 0;
        for(int next = i ; next < size ; next++){
            if(here < refine[next].start) break;
            int there = refine[next].start + refine[next].length;
            if(here >= there) pivot_max++;
        }
        ans = (ans >= pivot_max) ? ans : pivot_max;
    }
    // operation end
 
    // output
    dout1(ans);
    
    return 0;
}

어? 그럼 경우의수를 가지쳐주면 되나? 그래서 저대로 하면서 경우의 수를 cut 해주면 되겠다 생각을 하고 

다시 제출했더니 똑같이 시간초과였다.

#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
#define din1(a) scanf("%d",&a)
#define din2(a,b) scanf("%d%d",&a,&b)
#define din3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define din4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define dout1(a) printf("%d",a)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define start first
#define length second
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
//struct point{
//    int start;
//    int length;
//    point(){}
//    point(int is, int il):start(is), length(il){}
//};
 
typedef vector<pii> vp;
 
int n;
vp input;
vp refine;
 
pii crop_data(int s, int l){
    pii ret; 
    ret.start = (s>l)?l:s;
    ret.length = (l-s>0)?l-s:s-l;
    return ret;
}
 
int main(){
    // input 
    din1(n);
    for(int i = 0 ; i < n ; i++){
        int h,o; din2(h,o);
        pii ret = crop_data(h,o);
        input.pb(ret);
    }
    int dist; din1(dist);
 
    for(int i = 0 ; i < n ; i++){
        if(input[i].length <= dist) refine.pb(input[i]);
    }
    // input end
 
    int ans = 0;
    int pivot_max;
    // operation
    sort(refine.begin(), refine.end());
    int size = refine.size();
    for(int i = 0 ; i < size ; i++){
        if(size-i < ans) break; // cut; add code-1 
        if(i > 0 && refine[i].start == refine[i-1].start) continue; // cut; add code-2
        int here = refine[i].start + dist;
        pivot_max = 0;
        for(int next = i ; next < size ; next++){
            if(here < refine[next].start) break; // cut;
            int there = refine[next].start + refine[next].length;
            if(here >= there) pivot_max++;
        }
        ans = (ans >= pivot_max) ? ans : pivot_max;
    }
    // operation end
 
    // output
    dout1(ans);
    
    return 0;
}

그리고 한 3시간정도 계속 생각했다. 이거 문제를 이나 으로 풀어야하는데 어떻게하지.... 라고

그래서 min heap 두개를 사용하면 풀 수 있을 거 같다라는 생각이 들었다. 

하나의 우선순위큐에는 출발점들

두번째 우선순위큐에는 도착점들 

그러면 출발점과 도착점을 기준으로 잡고, 큐에서 각 점들을 뽑아내고 값이 넘어가면 더이상 큐에서 빼지 않고 넘기는 방법으로 작성했다.

#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
#include<queue>
#include<functional>
#define din1(a) scanf("%d",&a)
#define din2(a,b) scanf("%d%d",&a,&b)
#define din3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define din4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define dout1(a) printf("%d",a)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define start first
#define length second
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
//struct point{
//    int start;
//    int length;
//    point(){}
//    point(int is, int il):start(is), length(il){}
//};
 
typedef vector<pii> vp;
 
int n;
vp input;
vp refine;
 
pii crop_data(int s, int l){
    pii ret; 
    ret.start = (s>l)?l:s;
    ret.length = (l-s>0)?l-s:s-l;
    return ret;
}
 
int main(){
    // input 
    din1(n);
    for(int i = 0 ; i < n ; i++){
        int h,o; din2(h,o);
        pii ret = crop_data(h,o);
        input.pb(ret);
    }
    int dist; din1(dist);
 
    for(int i = 0 ; i < n ; i++){
        if(input[i].length <= dist) refine.pb(input[i]);
    }
    // input end
 
    int ans = 0;
    int count = 0;
    // 1 2 3 4 5 
    // greater<int> : 오름차순 1 2 3 4 5
    // less<int> : 내림차순 5 4 3 2 1
    int refine_size = refine.size();
    sort(refine.begin(), refine.end() );
    priority_queue<int, vector<int>, greater<int> > SQ;
    priority_queue<int, vector<int>, greater<int> > FQ;
    for(int i = 0 ; i < refine_size ; i++){
        SQ.push(refine[i].start);
        FQ.push(refine[i].start + refine[i].length);
    }
    // operation
    for(int i = 0 ; i < refine_size ; i++){
        int pivot_start = refine[i].start;
        int pivot_finish = pivot_start + dist;
        while(!SQ.empty()){
            int start = SQ.top();
            if(start < pivot_start) count--, SQ.pop();
            else if(start >= pivot_start) break;
        } // start count
        while(!FQ.empty()){
            int finish = FQ.top();
            if(finish <= pivot_finish)    count++, FQ.pop();
            else if(finish > pivot_finish) break;
        } // finish count 
 
        ans = (ans >= count) ? ans : count;        
    }    
    // operation end
 
    // output
    dout1(ans);
 
    return 0;
}