2586번: 소방차

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


흥미로운 문제였다.

$O((p+f)\lg(p+f))$

관찰을 통해 다음과 같은 몇 가지 특성을 발견할 수 있다.
1.
소방차와 펌프간 일대일 매칭을 1차원 좌표계에서 구간으로 표현하자.
구간들이 서로 완전히 포함하거나 완전히 분리된 형태가 최적해 안에 존재한다.
예를 들어, [1,3], [2,4] 가 최적해이면 이를 [1,4], [2,3]과 같이 바꿔줄 수 있다.
2.
최적해에 [l,r] 매칭이 존재하면 이 구간 안에 있는 소방차와 펌프는 모두 매칭되어야 한다.
그렇지 않으면 적당히 매칭을 바꿔서 더 최적인 상태를 만들 수 있기 때문이다.

이러한 두 특성에 따라 같은 레벨에서는 분리된 매칭만 존재하도록 매칭을 여러 개의 레벨로 나누어 관리할 수 있다.
주어진 입력을 위치를 기준으로 오름차순 정렬한 뒤,
펌프가 들어오면 현재 레벨에 넣어주고 레벨을 올리고 소방차가 들어오면 레벨을 내리고 현재 레벨에 넣어준다.

예를 들어, 펌프가 1, 4, 5 소방차가 2, 3 에 있으면
1 2 5
------
3 4
가 된다.

같은 레벨 상에선 펌프와 소방차가 번갈아 존재한다.
일반성을 잃지 않고 어떤 레벨의 처음이 펌프라고 해보자.
같은 레벨의 마지막이 소방차이면 앞에서부터 (펌프, 소방차)를 매칭 시켜주면 된다.
펌프이면
(펌프, 소방차), ..., (펌프, 소방차), 펌프, (소방차, 펌프), ..., (소방차, 펌프)
이런식으로 중간에 펌프 하나를 제외하고 매칭시킬 때 최소 호스 길이를 구하면 된다.

답은 모든 레벨의 최소 호스 길이 합이 된다.

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int MX = 2e5;
int p, f, pos = MX, res;
pair<int, int> a[MX];
vector<pair<int, int> > lv[MX * 2];
int main() {
    scanf("%d%d", &p, &f);
    for (int i = 0; i < p; i++) scanf("%d", &a[i].first), a[i].second = 0;
    for (int i = p; i < p + f; i++) scanf("%d", &a[i].first), a[i].second = 1;
    sort(a, a + p + f);
    for (int i = 0; i < p + f; i++) a[i].second ? lv[--pos].push_back(a[i]) : lv[pos++].push_back(a[i]);
    for (int i = 0; i < MX * 2; i++) {
        int s = 0, mini;
        for (int j = 1; j < lv[i].size(); j += 2) s += lv[i][j].first - lv[i][j - 1].first;
        mini = s;
        if (lv[i].size() & 1) for (int j = lv[i].size() - 1; j > 1; j -= 2)
            mini = min(mini, s += lv[i][j].first - lv[i][j - 1].first * 2 + lv[i][j - 2].first);
        res += mini;
    }
    printf("%d", res);
    return 0;
}