백준8987 수족관 3

작성일 | In

문제 링크

  • http://icpc.me/8987

문제 출처

  • 2013 KOI 고등부 4번

사용 알고리즘

  • 그리디
  • 세그먼트 트리
  • DFS

시간복잡도

  • $O(N log N) $

풀이

$K = 1$일 때는 물을 가장 많이 뺄 수 있는 곳에 구멍을 뚫는 것이 최적입니다.
$K > 1$일 때도 물을 가장 많이 뺄 수 있는 곳에 구멍을 계속해서 뚫는 것이 최적입니다. 그러나, $K > 1$인 경우에는 구멍을 뚫고 난 다음에, 각 수평 선분 별로 뺄 수 있는 물의 양을 갱신해야 하므로 귀찮습니다. 잘 처리하는 방법을 알아봅시다.

수평 선분 중 가장 위에 있는 것을 선택하면 구간을 둘로 나눌 수 있습니다.
구간을 둘로 나누는 것을 계속하면 이진 트리를 만들 수 있습니다. 이렇게 만들어지는 이진 트리에서 $[S, E]$를 관리하는 정점의 자식은 각각 $[S, K]$와 $[K+1, E]$를 관리합니다.

트리를 만들면서 해당 정점에서 뺄 수 있는 물의 양도 구할 수 있습니다. 각 정점에서 뺄 수 있는 물의 양을 우선 순위 큐에 넣고 가장 큰 K개를 선택해주면 됩니다.

구간을 둘로 나눌 때, 그 기준이 되는 곳은 세그먼트 트리를 이용해 구할 수 있습니다.
세그먼트 트리에 N번 쿼리를 날리고, 우선순위 큐에는 N번의 push연산과 K번의 pop연산을 날리기 때문에 $O(N log N)$에 문제를 풀 수 있습니다.

전체 코드

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

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

int n, k;
ll x[1 << 18];
ll y[1 << 18];

p tree[1 << 19];
int bias = 1 << 18;
void init(){
	for(int i=0; i<n; i++) tree[i | bias] = {y[i], i};
	for(int i=bias-1; i; i--) tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
}
int query(int l, int r){
	l |= bias, r |= bias;
	p ret(1e18, 1e18);
	while(l <= r){
		if(l & 1) ret = min(ret, tree[l++]);
		if(~r & 1) ret = min(ret, tree[r--]);
		l >>= 1, r >>= 1;
	}
	return ret.y;
}

priority_queue<ll> pq;
int h;

ll f(int s, int e){
	if(s >= e){
		return 0;
	}
	int idx = query(s, e-1);
	int prv = h;
	h = y[idx];
	ll t1 = f(s, idx), t2 = f(idx+1, e);
	pq.push(min(t1, t2));
	h = prv;
	return max(t1, t2) + (x[e] - x[s]) * (y[idx] - h);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; n >>= 1;
	for(int i=0; i<n; i++){
		cin >> x[i] >> y[i];
		cin >> x[i] >> y[i];
	}
	cin >> k;
	init();
	ll t = f(0, n-1);
	pq.push(t);
	ll ans = 0;
	for(int i=0; i<k; i++){
		if(!pq.size()) break;
		ans += pq.top(); pq.pop();
	}
	cout << ans;
}