BOJ 28703 - Double It
우선, 에서 가장 큰 수는 를 곱할 일이 없다.
그렇다고 하자.
가 있을 때, 와 더 가까워지기 위해서는 가 처럼 커져야하는데, 어떤 경우에도 이기 때문에 모순이다.
따라서 를 기준으로 삼고 나머지 모든 수들은 이하까지만 배를 하거나 거기서 딱 한 번 더 배를 하거나이다.
이는 이하까지 두배를 한 것들을 정렬해서 한 번씩 곱해주며 모두 비교하는 것으로 정답을 에 구할 수 있다.
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;
}
Comments