11991번: Fenced In (Platinum)

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


$O((n+m)\lg (n+m))$

(n+1)*(m+1)개의 지점을 노드로, 인접한 선분의 길이를 인접한 노드로 이동하는데 드는 비용으로 놓으면 최소신장트리를 구해서 문제를 해결 할 수 있다.
크루스칼 알고리즘을 쓸 때 작은 비용의 간선부터 그리디하게 선택할 수 있음을 알고 있을 것이다.
같은 행, 열에 존재하는 선분 길이는 모두 같으므로 한꺼번에 최소신장트리에 포함시킬 수 있다.
이를 이용한 방법은 다음과 같다.

1. 행, 열을 구분하여 나눠진 간격을 배열에 저장하고 오름차순 정렬한다.
2. 작은 간격부터 보면서 행 간격, 열 간격 모두 등장할 때까지 해당 줄에 있는 인접한 지점 사이에 있는 선분을 제거한다.
3. 행, 열 간격이 모두 등장한 이후라면 주어진 연결된 지점들과 연결할 수 있는 최소한의 선분만 제거한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, A, B, a[25002], b[25002], ac, bc;
long long r;
pair<int, int> p[50002];
int main() {
    scanf("%d%d%d%d", &A, &B, &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= m; i++) scanf("%d", b + i);
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + m);
    a[n + 1] = A;
    b[m + 1] = B;
    for (int i = 0; i <= n; i++) p[i] = { a[i + 1] - a[i],0 };
    for (int i = 0; i <= m; i++) p[i + n + 1] = { b[i + 1] - b[i],1 };
    sort(p, p + n + m + 2);
    for (int i = 0; i<n + m + 2; i++) {
        if (!ac || !bc) r += (long long)(p[i].second ? n : m)*p[i].first;
        else r += (long long)(p[i].second ? n + 1 - ac : m + 1 - bc)*p[i].first;
        p[i].second ? bc++ : ac++;
    }
    printf("%lld", r);
    return 0;
}