티스토리 뷰

알고리즘 관련/BOJ

BOJ)15589 Lifeguards (Silver)

JASON 자손9319 2018. 6. 26. 17:20

문제: icpc.me/15589


n명의 인원이 1차원 구간을 커버하는 데  이중에서 한 인원을 제외했을 때 커버가능한 최대 구간을 출력하는 문제이다.


전체 구간에서 하나를 제외 하였을 때 최대 구간을 구하면 되므로


하나의 구간에서 다른 구간에 영향을 받지 않고 유일하게 커버되는 구간 중 최솟값을 구하여 전체 구간에서 빼주면 답이 된다.


각각의 구간에서 독립적으로 커버하는 구간은 왼쪽에서 부터, 오른쪽에서 부터 , 두번 스위핑하여 구할 수 있다. 


자세한 설명은 소스코드로 대신하겠다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,x,y;
vector<pair<int,int>> vt;
vector<int> l,r;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&x,&y);
        vt.push_back({x,y});
    }
    sort(vt.begin(),vt.end());
    l.assign(n,0),r.assign(n,0);
    int rmax=0;
    for(int i=0;i<n;i++){
        r[i]=rmax;
        rmax=max(rmax,vt[i].second);
    }
    int lmin=1e9;
    for(int i=n-1;i>=0;i--){
        l[i]=lmin;
        lmin=min(lmin,vt[i].first-1);
    }
    int indcover=1e9;
    for(int i=0;i<n;i++){
        int ll=max(vt[i].first,r[i]);
        int rr=min(vt[i].second-1,l[i]);
        if(ll>rr)indcover=0;
        else indcover=min(indcover,rr-ll+1);
    }
    int cover=0;
    int currl=0,currr=-1;
    for(int i=0;i<n;i++){
        if(currr>=vt[i].first)
            currr=max(currr,vt[i].second-1);
        else{
            cover+=(currr-currl+1);
            currl=vt[i].first,currr=vt[i].second-1;
        }
    }
    cover+=(currr-currl+1);
    printf("%d\n",cover-indcover);
    return 0;
}
cs

 

'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)15745 Snow Boots  (0) 2018.07.03
BOJ)13274 수열  (0) 2018.07.02
BOJ)15589 Lifeguards (Silver)  (0) 2018.06.26
BOJ)14965 Lozinke  (0) 2018.06.26
BOJ)11964 Fruit Feast  (0) 2018.06.25
BOJ)11046 팰린드롬??  (0) 2018.06.25
댓글
댓글쓰기 폼