백준2586 소방차

작성일 | In

문제 링크

  • http://icpc.me/2586

문제 출처

  • 2005 KOI 고등부 3번

사용 알고리즘

  • DP
  • 그리디

시간복잡도

  • $O((P+F) \log (P+F))$

풀이

최적해가 어떤 형태인지, 혹은 특정한 형태를 강제할 수 있는지 생각해봅시다.

소방차와 펌프를 매칭하는 것을 구간이라고 생각하면, 구간들이 서로를 완전히 포함하거나 완전히 분리된 형태의 최적해가 존재합니다.
Proof) $a \leq b \leq c \leq d$ 일 때 $[a, c]$, $[b, d]$를 매칭하는 것이 최적이라면 $[a, d]$, $[b, c]$로 바꿔도 거리는 동일합니다.

최적해에 $[l, r]$ 매칭이 존재한다면, 이 구간 안에 있는 소방차와 펌프는 모두 매칭되어 있습니다.
Proof) 그렇지 않으면 적당히 바꿔서 거리를 더 줄일 수 있습니다.

구간의 포함 관계를 트리(or 포레스트)로 생각할 수 있습니다. 이때 같은 depth에서는 모든 구간이 분리되어 있습니다.

펌프와 소방차의 depth는 아래 과정을 통해 결정할 수 있습니다.

  1. 입력으로 들어온 모든 좌표를 정렬
  2. 좌표 순서대로 보면서, 펌프/소방차에 따라 다음 과정을 수행
    • 펌프가 나오면 현재 depth에 넣고 depth++
    • 소방차가 나오면 –depth하고 depth에 넣음

같은 depth에서는 펌프와 소방차가 교대로 등장합니다.
어떤 depth에 원소가 짝수 개 있다면 순서대로 매칭하면 됩니다.
홀수인 경우, 하나를 빼고 매칭하는 $K$가지 경우를 $O(K)$만에 모두 확인해주면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n, m, k;
p a[202020];
vector<p> v[404040];
ll ans;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m; k = n + m;
    for(int i=1; i<=n; i++) cin >> a[i].x, a[i].y = 0;
    for(int i=1; i<=m; i++) cin >> a[i+n].x, a[i+n].y = 1;
    sort(a+1, a+k+1);

    int now = k;
    for(int i=1; i<=k; i++){
        if(a[i].y == 0) v[now++].push_back(a[i]);
        else v[--now].push_back(a[i]);
    }
    for(int i=0; i<404040; i++) if(v[i].size()) {
        ll t = 0;
        for(int j=1; j<v[i].size(); j+=2) t += abs(v[i][j].x - v[i][j-1].x);
        if(~v[i].size() & 1){ ans += t; continue; }
        ll mn = t;
        for(int j=v[i].size()-1; j-2>=0; j-=2){
            t += abs(v[i][j].x - v[i][j-1].x) - abs(v[i][j-1].x - v[i][j-2].x);
            mn = min(mn, t);
        }
        ans += mn;
    }
    cout << ans;
}