코드 복사/붙여넣기 하는 당신이 아름답습니다.

13209 : 검역소

풀이

이분 탐색(log n)을 돌면서 그리디(n)을 돌리면 O(n log n)에 해결할 수 있다.

priority_queue를 사용하기 전에 벡터를 써서 정렬하는 생각을 먼저 했지만

코딩이 괴랄해져서 포기하고 우선순위큐를 사용했다.

바이너리 서치의 mid를 비축할 백신의 수라고 두고, 주어진 검역소만으로 mid를 충족시킬 수 있는지 그리디로 풀면 된다.

싸이클이 없고 임의의 a에서 b로 가는 경로가 단 하나이기 때문에 그리디로 풀 수 있다!

dfs의 리턴값은 항상 mid를 넘지 않음이 보장된다. 물론 인구수가 mid를 넘을 수는 있다.

그건 left = max((int)left, people[i]) 이걸로 처리해주면 된다.

그리고 큐를 보면서 (top + people[now])가 mid 보다 작아질 때 까지 큰 것 부터 컷 해주면 된다.

의식의 흐름대로 썼더니 글이 좀 이상하다. (?)

코드

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <memory.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int n_ = 1e5 + 1;

bool vst[n_];
int n, k, wall_cnt, people[n_];
ll vac_max;
vi adj[n_];

ll dfs(int now) {
	ll ret_val, ret_sum = 0;
	priority_queue<ll> pq;

	vst[now] = true;
	for (auto next : adj[now]) {
		if (vst[next]) continue;
		ret_val = dfs(next);
		ret_sum += ret_val;
		pq.push(ret_val);
	}

	while (!pq.empty() && ret_sum + people[now] > vac_max) {
		++wall_cnt;
		ret_sum -= pq.top();
		pq.pop();
	}
	return ret_sum + people[now];
}

int main() {
	int tc, i;
	scanf("%d", &tc);
	while (tc--) {
		ll l = 0, r = 0, ans = 0;
		scanf("%d %d", &n, &k);
		for (i = 1; i <= n; ++i) {
			scanf("%d", &people[i]), adj[i].clear();
			l = max((int)l, people[i]), r += people[i];
		}
		for (i = 0; i < n - 1; ++i) {
			int a, b;
			scanf("%d %d", &a, &b);
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		while (l <= r) {
			ll m = (l + r) / 2;
			wall_cnt = 0, vac_max = m;
			memset(vst, 0, sizeof(vst));
			dfs(1);
			if (wall_cnt <= k) r = m - 1, ans = m;
			else l = m + 1;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-02-16 23:15

Read more posts by this author