백준 1417 국회의원 선거

https://www.acmicpc.net/problem/1417

1417번: 국회의원 선거

우선순위 큐 (Priority_queue)

다솜이가 후보 중 가장 많은 표를 가져야 한다.

= 다솜이가 다솜이를 제외한 다른 후보 중 가장 많은 표를 가질 후보보다 많은 표를 가져야 한다.

=> 다솜이를 제외한 다른 후보를 우선순위 큐에 넣어 가장 많은 표를 가진 후보를 선택하도록 한다.

 

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <queue>

int main(){
    fio;
    int N; cin >> N;
    int dasom; cin >> dasom;
    priority_queue<int> candidate;
    for(int i=0; i < N-1; i++){
        int tmp; cin >> tmp;
        candidate.push(tmp);
    }

    //
    int cnt = 0;
    while(!candidate.empty() && dasom <= candidate.top()){
        int now_top = candidate.top();
        candidate.pop();
        dasom++;
        candidate.push(now_top - 1);
        cnt++;
    }
    cout << cnt;

    return 0;
}