BOJ 28703 - Double It

BOJ 28703 - Double It

우선, $A$에서 가장 큰 수는 $2$를 곱할 일이 없다.

그렇다고 하자.

$a < b$ 가 있을 때, $2b$ 와 더 가까워지기 위해서는 $a$ 가 $2a, 4a, 8a, \dots$ 처럼 커져야하는데, 어떤 경우에도 $nb-na \ge b-a$ 이기 때문에 모순이다.

따라서 $\text{Max}(A)$ 를 기준으로 삼고 나머지 모든 수들은 $A$ 이하까지만 $2$배를 하거나 거기서 딱 한 번 더 $2$배를 하거나이다.

이는 $A$ 이하까지 두배를 한 것들을 정렬해서 한 번씩 곱해주며 모두 비교하는 것으로 정답을 $O(n\log n)$ 에 구할 수 있다.

void solve() {  
   int n;  
   cin >> n;  
   if (n == 1) {  
      cout << 0;  
      return;  
   }  
   vi a(n);  
   fv(a);  
   sort(all(a));  
   for (int i = 0; i < sz(a) - 1; i++)  
      while (a[i] * 2 <= a.back()) a[i] *= 2;  
   sort(a.begin(), a.end() - 1);  
   int ans = a.back() - a.front();  
   deque<int> b(all(a));  
   for (int i = 0; i < sz(a) - 1; i++) {  
      b.pb(b.front() * 2);  
      b.pop_front();  
      mina(ans, b.back() - b.front());  
   }  
   cout << ans;  
}