28703: Double It

문제 링크

28703: Double It

구현 방식

• min heap을 이용해서 최솟값이 초기의 최댓값(mx)보다 작을때까지 "배열에서 원하는 수 하나를 골라서 2를 곱합니다"의 연산을 수행해주었다
• cpp에서 priority_queue 사용하는 방법은 아래와 같다

priority_queue<int, vector<int>, greater<int>> min_heap;

• 최소힙

priority_queue<int, vector<int>, less<int>> max_heap;

• 최대힙

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;


int main() {
    int N; cin >> N;

    priority_queue<int, vector<int>, greater<int>> Q;
    int mx = 0;
    for (int i=0; i<N; i++){
        int v; cin >> v;
        mx = max(mx, v);
        Q.push(v);
    }

    int curr_mx = mx;
    int diff = curr_mx - Q.top();

    while (Q.top() < mx){
        int v = Q.top(); Q.pop();
        diff = min(diff, curr_mx - v);
        curr_mx = max(curr_mx, v*2);
        Q.push(v*2);
    }

    cout << min(curr_mx - Q.top(), diff);

    return 0;
}

import sys
import heapq

N = int(sys.stdin.readline()[:-1])
A = []
mx = 0

for v in map(int, sys.stdin.readline()[:-1].split()):
    mx = max(mx, v)
    heapq.heappush(A, v)

curr_mx = mx
diff = curr_mx - A[0] #현재 최댓값과 최솟값의 차이

while A[0] < mx:
    v = heapq.heappop(A)
    diff = min(diff, curr_mx - v)
    curr_mx = max(curr_mx, 2*v)
    heapq.heappush(A, 2*v)
print(min(curr_mx-A[0], diff))