BOJ 28245 - 배고파(Hard)
모든 쌍을 미리 전처리해둔다. 대략 개가 나온다.
이제 개의 테스트케이스마다 그 중에서 가장 가까운 것을 naive하게 찾거나 이분탐색으로 빠르게 찾아서 실수없이 가장 가까운 것을 출력해주면 된다.
void solve() {
int n;
cin >> n;
vector<array<int, 3>> cand;
for (int i = 0, I = 1; i <= 60; i++) {
for (int j = i, J = I; j <= 60; j++) {
cand.pb({I + J, i, j});
J *= 2;
}
I *= 2;
}
uniq(cand);
for (int i = 0; i < n; i++) {
int m;
cin >> m;
array<int, 3> a = {-1, -1};
array<int, 3> b = {-1, -1};
array<int, 3> c = {-1, -1};
for (int j = 0; j < sz(cand); j++) {
if (cand[j][0] < m) {
if (a[0] == -1 || cand[j][0] > a[0] || (cand[j][0] == a[0] && cand[j][1] < a[1]))
a = cand[j];
} else if (cand[j][0] == m) {
if (b[0] == -1)
b = cand[j];
} else {
c = cand[j];
break;
}
}
if (b[0] != -1) {
cout << b[1] << ' ' << b[2] << endl;
} else if (a[0] == -1) {
cout << c[1] << ' ' << c[2] << endl;
} else {
if (m - a[0] <= c[0] - m) {
cout << a[1] << ' ' << a[2] << endl;
} else {
cout << c[1] << ' ' << c[2] << endl;
}
}
}
}
빠른 풀이Permalink
두 의 거듭제곱수의 합이기 때문에 비트로 표현하면 비트가 항상 두 개가 켜져있거나 한개가 켜져있는 수가 된다.
의 비트수에 따라 케이스워크를 갈긴다
비트 1개
은 따로 처리를 해주고, 나머지는 가 된 것이므로 을 그대로 둔다.
비트 2개
그 켜진 비트 두 개가 가 된다.
비트 3개
을 줄이거나 늘릴 수 있다.
줄일 경우엔 가장 큰 두 비트를 남기고 버려준다.
늘릴 경우엔 두 번째로 큰 비트를 올림해준다.
혹은
Comments