BOJ 27846 - Bakery
문제가 길고 어렵다.
를 모두 만족하는 를 찾는 문제로 치환할 수 있어 선형 대수학 문제인가 했지만, 단순 binary search문제였다.
일단 산뜻하게 에 대해서 이분 탐색을 돌려주자.
가 mooney이고 결국 특정 시점 이후로는 항상 가능할 것이기 때문에 이분 탐색이 가능하다.
이 때, 이분탐색의 범위를 로 잡아준다.
왜냐면 를 초과해서 시간을 뺄 수가 없기 때문이다.
현재 검사하고 있는 값이 이라고 할 때, 을 만족하는 에서 를 기준으로 몇개가 가능한지 범위를 좁혀나간다고 해보자.
의 범위는 처음에 이다.
일단 무조건 줄여야 하는 양이 머핀은 최대 개 밖에 못줄이기 때문에 이란 값이 나온거고,
최대로 쿠키를 줄일 수 있는 횟수는 이다.
이제 모든 조건들에 대해 검사를 해볼 차례인데, 가 있다고 하자.
일단 번째 친구는 여야 한다. 그렇지 않으면 더 효율이 좋은걸로만 시간을 단축시킨다해도 만족시키가 불가능하다.
어떤 에 대해 위 조건을 만족한다고 하자.
인 경우엔 뭘 감소시켜도 상관 없으므로 skip
인 경우, 최대 의 개수가 정해져 있을 것이다. 그걸 구해서 의 범위를 좁힌다.
인 경우, 최소 의 개수가 정해져 있을 것이다. 그걸 구해서 의 범위를 좁힌다.
이 최대 최소 의 값을 구하는건 수식으로 구해도 되고 이분 탐색을 한 번 더 써도 된다.
인 경우를 수식화해보면 이므로 에 대해 정리하면
대충 요런식으로 정리가 되면서 최대 의 개수를 구해 제한할 수 있게 될 것이다.
이건 단순히 이분 탐색을 한번 더 돌리는게 편할지도.. 밑에 코드는 이분탐색이다.
이제 어떤 에 대해 모든 친구들이 위 조건을 통과한다면 은 모두를 만족시키기에 가능한 값이 된다.
이런식으로 binary search를 돌려주면 된다.
void solve() {
int n, tc, tm;
cin >> n >> tc >> tm;
vector<array<int, 3>> arr;
for (int i = 0; i < n; i++) {
int a, b, c;
cin >> a >> b >> c;
int spare = a * tc + b * tm - c;
arr.pb({a, b, spare});
}
int L = 0, R = tc + tm - 2, A = -1;
while (L <= R) {
int M = R - (R - L) / 2;
bool can = 1;
// 최대로 tc 를 줄일 수 있는 양
int max_x = tc - 1;
// 일단 무조건 tc 를 줄여야 하는 양
int min_x = M - (tm - 1);
for (int i = 0; i < n; i++) {
int denom = max(arr[i][0], arr[i][1]);
int need = (arr[i][2] + denom - 1) / denom;
if (need > M) {
can = 0;
break;
}
// arr[i][0] == arr[i][1] 인 경우 아무거나 해도 상관없으므로 신경쓸필요 없다.
auto get_minimum_x = [&]() {
int l = 0, r = M, ret = -1;
while (l <= r) {
int mid = r - (r - l) / 2;
if (arr[i][0] * mid + arr[i][1] * (M - mid) >= arr[i][2])
ret = mid, r = mid - 1;
else
l = mid + 1;
};
return ret;
};
auto get_maximum_x = [&]() {
int l = 0, r = M, ret = -1;
while (l <= r) {
int mid = l + r >> 1;
if (arr[i][0] * mid + arr[i][1] * (M - mid) >= arr[i][2])
ret = mid, l = mid + 1;
else
r = mid - 1;
};
return ret;
};
if (arr[i][0] > arr[i][1]) {
// X가 특정 이상개여야 한다.
min_x = max(min_x, get_minimum_x());
}
if (arr[i][0] < arr[i][1]) {
// X가 특정 이하개여야 한다.
max_x = min(max_x, get_maximum_x());
}
}
if (min_x > max_x) can = 0;
if (can) A = M, R = M - 1;
else L = M + 1;
}
cout << A << endl;
}
Comments