백준 27896 - 특별한 서빙 (C++)

문제 문제 링크 BOJ 27896 - 특별한 서빙 문제 요약 $N$명의 학생들의 불만도가 주어진다. $M$을 넘지 않도록 급식을 분배할 때 필요한 최소 가지의 개수를 구해보자.

제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N ≤ 200,000$ $1 ≤ M ≤ 10^9$ $0 ≤ x_i ≤ 10^9$ 알고리즘 분류 자료 구조(data structures) 그리디 알고리즘(greedy) 우선순위 큐(priority_queue) 풀이 우선 보면 주어진 순서를 유지해야 한다고 한다. 그렇다면 일단 파묻튀를 먹이다가, 불만도의 합이 $M$ 을 넘는 순간이 온다면 그동안의 $x_i$ 중 가장 큰 녀석에게 가지를 주는 것이 이득이지 않겠는가?

이러한 상황에 더없이 편한 녀석이 우선순위 큐다. 이.....