[백준 28703번] Double it (C++)

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

maxPq, minPq 우선순위 큐 2개를 이용해서 하나씩 뽑으면서 차이의 최솟값을 갱신해나가면 된다.

문제는 위의 과정의 종료조건인데, 구해야 하는 것이 최대값-최솟값의 차이기 때문에 만약 입력으로 주어지는 모든 수를 2배를 할 필요가 없다. 모든수가 2배가 되면 1/2배를 할 수 있고 그럼 2배가 된 상태보다 차이도 1/2이 되므로 모든 수가 2배이상으로 커지는 것은 의미가 없다.

따라서 모든 수가 2배가 되기 전까지가 반복문의 종료조건이 된다.

 

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, num;
	cin >> n;
	priority_queue<int> maxPq;
	priority_queue<int, vector<int>, greater<int>> minPq;
	for(int i = 0; i < n; i++){
		cin >> num;
		maxPq.push(num);
		minPq.push(num);
	}
	
	int limit = maxPq.top();
	int diff = 1000000001;
	while(minPq.top() <= limit){
		int mn = minPq.top();
		int mx = maxPq.top();
		diff = min(diff, mx-mn);
		minPq.pop();
		minPq.push(mn*2);
		maxPq.push(mn*2);
	}
	cout << diff;
}