백준 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$ 중 가장 큰 녀석에게 가지를 주는 것이 이득이지 않겠는가?

이러한 상황에 더없이 편한 녀석이 우선순위 큐다. 이를 이용해 뚝딱 풀어내자.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
priority_queue <int> Q;
int n, m, r;
 
int main()
{
    cin >> n >> m;
    for (int i, s{}; n--;)
    {
        scanf("%d", &i);
        Q.push(i); s += i;
        while (s >= m) r++, s -= Q.top() * 2, Q.pop();
    }
    cout << r;
}

comment

끝