BOJ 26393 - Čokolade
가 최소가 되어야 한다.
이득을 라고 정의해보자.
인 걸 살 때 얻는 이득은 이다.
인 걸 살 때 얻는 이득은 내가 를 지불하고 가 를 지불하므로 이다.
정렬된 를 를 pivot으로 두고 두 구간으로 나눴을 때 왼쪽과 오른쪽의 끝부터 택하는게 항상 더 이득이다.
가 작다면 이걸 투포인터로 찾을 수 있겠지만 이 문제에선 성질을 관찰해서 삼분탐색을 이용할 수 있다.
을 오른쪽 끝에서부터 개를 택할 때, 그럼 왼쪽에선 개만큼 택하고 이득값이라고 하자.
이 uni-modal함을 보일수있을까?
나는 일단 못보이겠다. 찍어서 맞췄다 ㅈㅅ. 하지만 밑에 해설을 보면 왜 uni-modal한지 알 수 있다.
에디토리얼 해설을 보면 삼분탐색 말고 이분탐색으로만 풀 수 있다.
일단 왼쪽 초콜릿을 개 고르고 오른쪽 초콜릿을 몇개를 취할지를 이분탐색으로 구하면 된다.
이분탐색이 끝나는 지점은 오른쪽 초콜릿에서 개를 취했을 때 그걸 취했을 때 더 이득이 되지 않는 시점이다.
그 이전 초콜릿까지만 오른쪽에서 취해주면 된다.
아래는 삼분탐색 코드다.
void solve() {
int n, q;
cin >> n >> q;
vi c(n), p(n + 1);
fv(c);
sort(all(c));
for (int i = 0; i < n; i++) p[i + 1] = p[i] + c[i];
auto sum = [&](int l, int r) { return p[r + 1] - p[l]; };
while (q--) {
int k, m;
cin >> k >> m;
int pivot = ubi(c, k);
int L = pivot, R = n - pivot;
int l = max<int>(0, m - L), r = min(m, R);
auto val = [&](int x) -> int {
int left = m - x;
int right = x;
int ret = -sum(0, left - 1);
ret += sum(n - right, n - 1) - 2 * k * right;
return ret;
};
int ans = -2e18;
while (l < r - 3) {
int p = (l * 2 + r) / 3, q = (l + 2 * r) / 3;
int pv = val(p), qv = val(q);
if (pv > qv) r = q;
else l = p;
}
for (int i = l; i <= r; i++)maxa(ans, val(i));
cout << -ans << endl;
}
}
Comments