[BOJ/백준][Gold2] 13334 : 철로 (C++)

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

13334번: 철로

 

 

[난이도] Gold2
[유형] 스위핑

[풀이]
길이 d의 선을 평행이동 시키면서 어느시점에 i가 포함되고 빠지는지를 누적하면서 계산해주면 된다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,d,ans;
vector<pair<int,int>> t,a;
int main(){
    scanf("%d",&N);
    int j=0;
    for(int i=0;i<N;i++){
        int u,v;  
        scanf("%d%d",&u,&v);
        if(u>v) swap(u,v);
        t.push_back({u,v});
    }
    scanf("%d",&d);

    for(auto p : t){
        if(p.second-p.first>d) continue;
        a.push_back({p.first,1});
        a.push_back({p.second-d,-1});
    }
    sort(a.begin(),a.end());
    int cnt=0;
    for(auto p : a){       
        cnt-=p.second;
        ans=max(ans,cnt);
    }
    printf("%d",ans);
}

 

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/13334.cpp