[백준 / BOJ] C++ 28703 Double It

28703번: Double It

 

문제

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

28703번: Double It

 

 

풀이

본 대회 때는 삽질만 종일 하다가 결국 못 푼 문제. 에디토리얼 참고해서 풀었다.

 

배열의 최솟값을 두배로 증가시켜 가며 최댓값과의 차를 최솟값으로 비교하며 업데이트한다.

이를 최솟값이 처음 배열의 최댓값보다 작을 때만 계속해서 반복한다.

최솟값 관리를 우선순위 큐로 하면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m = 0;
  cin >> n;
  priority_queue<int> q;
  while (n--) {
    int x;
    cin >> x;
    m = max(m, x);
    q.push(-x);
  }
  int mx = m;
  int ans = mx + q.top();
  while (-q.top() < m) {
    int x = -q.top();
    q.pop();
    ans = min(ans, mx - x);
    mx = max(mx, 2 * x);
    q.push(-2 * x);
  }
  cout << min(mx + q.top(), ans);
  return 0;
}