풀이
이분 탐색(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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이