[C++] (우선순위 큐) 큰 숫자만 계속 고르기

큰 숫자만 계속 고르기

n개의 숫자가 주어졌을 때 그 중 가장 큰 숫자를 골라 1씩 빼는 작업을 m번 반복하려고 합니다. 이를 반복한 이후 남아있는 숫자들 중 최댓값을 구하는 프로그램을 작성해보세요. 단, 가장 큰 숫자가 여러 개라면 이 중 아무거나 하나를 골라 진행하면 됩니다.

 

 

입출력 예제

입력:

5 4
1 5 4 2 1

출력:

3

 

 

 

처음에 [1, 5, 4, 2, 1] 이 있습니다. 

이 중 최대를 골라 1을 빼주면 결과는 [1, 4, 4, 2, 1]이 됩니다. 

(1회) 이 중 최대를 골라 1을 빼주면 결과는 [1, 3, 4, 2, 1]이 됩니다. 

(2회) 이 중 최대를 골라 1을 빼주면 결과는 [1, 3, 3, 2, 1]이 됩니다. 

(3회) 이 중 최대를 골라 1을 빼주면 결과는 [1, 2, 3, 2, 1]이 됩니다. 

(4회) 따라서 남아있는 숫자들 중 최댓값은 3이 됩니다.

 

 

 

풀이

#include <iostream>
#include <queue>

using namespace std;

int main() {
    int n, m;
    priority_queue<int> pq;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        int num1;
        cin >> num1;
        pq.push(num1);
    }
    for(int i = 0; i < m; i++){
        int num2;
        num2 = pq.top() - 1;
        pq.pop();
        pq.push(num2);
    }
    cout << pq.top();
    return 0;
}