백준 31741 - 구간 덮기

step 1

선분을 1개, 2개, 3개 쓰는 경우에 대해 각각 답을 구하고 그 중 가장 좋은 것을 출력하면 됩니다.

 

1개를 쓰는 경우 : 전체를 다 덮는 선분이 있어야 합니다. 이 경우 답은 0입니다.

 

선분들을 (A)시작점을 포함하는 것, (B)시작점과 끝점 사이에 있는 것, (C)끝점을 포함하는 것 3 종류로 나눌 수 있습니다. 지금부터 (C)에서 고른 선분을 $C$, 그 선분의 시작점을 $C_x$, 끝점을 $C_y$ 이런 식으로 쓰겠습니다.

 

2개 쓰는 경우 : (A)와 (C)의 조합으로 만들 수 있습니다. $C$ 기준으로 $A$를 찾는다고 할 때 (A)에 있는 선분들 중 끝점이 $C_y$보다 큰 선분들 중 끝점이 가장 작은 선분이 최적의 선분입니다. set에 A의 끝 점을 전부 넣어두면 쉽게 찾을 수 있고 이분 탐색을 사용하셔도 됩니다.

 

step 2

3개 쓰는 경우 : (A), (B), (C)를 1개씩 사용해서 만들 수 있습니다. (A)나 (C)를 2개 쓰는 경우는 항상 최적이 아니고 (B)를 2개 쓰는 경우는 선분을 다 덮을 수 없습니다.

$B$에 대해서 가장 좋은 $A$를 찾습니다. 이 과정은 2개 쓰는 경우와 똑같이 진행하면 됩니다.

$B$에 대해서 가장 좋은 $C$를 찾습니다. (A)의 끝점 대신 (C)의 시작점을 기준으로 위와 똑같이 진행하면 됩니다. 이때는 시작점이 $B_y$보다 작은 선분들 중 시작점이 가장 큰 선분을 찾으면 됩니다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#include <cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
using namespace std;
struct data {
    long long int x, y;
}b[2000000];
set<long long int> ss,ee;
int main() {
    long long int n, s, e, i,minn=2100000000;
    scanf("%lld%lld%lld", &n, &s, &e);
    for (i = 1;i <= n;i++) {
        scanf("%lld%lld", &b[i].x, &b[i].y);
        if (b[i].x <= s && b[i].y >= e) { printf("0"); return 0; }
        if (b[i].x <= s && b[i].y >= s) {
            ss.insert(b[i].y);
        }
        if (b[i].x <= e && b[i].y >= e) {
            ee.insert(b[i].x);
        }
    }
    if (ss.size() == 0 || ee.size() == 0) { printf("-1"); return 0; }
    for (i = 1;i <= n;i++) {
        if (b[i].x <= e && b[i].y >= e) {
            auto it = ss.lower_bound(b[i].x);
            if (it != ss.end()) {
                minn = min(minn, (*it) - b[i].x);
            }
        }
        if (b[i].x > s && b[i].y < e) {
            auto it = ss.lower_bound(b[i].x);
            long long int val = 0;
            if (it == ss.end()) continue;
            if (it != ss.end()) {
                val = (*it) - b[i].x;
            }
            auto it2 = ee.upper_bound(b[i].y);
            if (it2 == ee.begin()) continue;
            if (it2 != ee.begin()) {
                it2--;
                val += b[i].y - (*it2);
            }
            if ((*it) > (*it2)) val += (*it) - (*it2);
            minn = min(minn, val);
        }
    }
    printf("%lld", minn== 2100000000 ? -1 : minn);
    return 0;
}