BOJ 27846 - Bakery

BOJ 27846 - Bakery

문제가 길고 어렵다.

$a_ix+b_iy \ge a_i \cdot t_c + b_i \cdot t_m - c_i$ 를 모두 만족하는 $x,\,y$를 찾는 문제로 치환할 수 있어 선형 대수학 문제인가 했지만, 단순 binary search문제였다.

일단 산뜻하게 $x+y$ 에 대해서 이분 탐색을 돌려주자.

$x+y$가 mooney이고 결국 특정 시점 이후로는 항상 가능할 것이기 때문에 이분 탐색이 가능하다.

이 때, 이분탐색의 범위를 $[0,\,t_c+t_m-2]$ 로 잡아준다.

왜냐면 $t_c+t_m-2$ 를 초과해서 시간을 뺄 수가 없기 때문이다.

현재 검사하고 있는 값이 $M$ 이라고 할 때, $x+y=M$ 을 만족하는 $x,\,y$에서 $x$를 기준으로 몇개가 가능한지 범위를 좁혀나간다고 해보자.

$x$의 범위는 처음에 $[M-t_m+1,\,t_c-1]$ 이다.

일단 무조건 줄여야 하는 양이 머핀은 최대 $t_m-1$ 개 밖에 못줄이기 때문에 $M-t_m+1$ 이란 값이 나온거고,

최대로 쿠키를 줄일 수 있는 횟수는 $t_c-1$ 이다.

이제 모든 조건들에 대해 검사를 해볼 차례인데, $a_i,\,b_i,\,k_i(=a_i \cdot t_c + b_i \cdot t_m - c_i)$ 가 있다고 하자.

일단 $i$ 번째 친구는 $Max(a_i,b_i)M \ge k_i$ 여야 한다. 그렇지 않으면 더 효율이 좋은걸로만 시간을 단축시킨다해도 만족시키가 불가능하다.

어떤 $i$에 대해 위 조건을 만족한다고 하자.

$a_i=b_i$ 인 경우엔 뭘 감소시켜도 상관 없으므로 skip

$a_i<b_i$ 인 경우, 최대 $x$의 개수가 정해져 있을 것이다. 그걸 구해서 $x$의 범위를 좁힌다.

$a_i>b_i$ 인 경우, 최소 $x$의 개수가 정해져 있을 것이다. 그걸 구해서 $x$의 범위를 좁힌다.

이 최대 최소 $x$의 값을 구하는건 수식으로 구해도 되고 이분 탐색을 한 번 더 써도 된다.

$a_i<b_i$ 인 경우를 수식화해보면 $a_ix+b_i(M-x)\ge k_i$ 이므로 $x$에 대해 정리하면

$$ (a_i-b_i)x \ge k_i-b_iM \\ x \ge \dfrac {k_i-b_iM}{a_i-b_i} $$

대충 요런식으로 정리가 되면서 최대 $x$ 의 개수를 구해 제한할 수 있게 될 것이다.

이건 단순히 이분 탐색을 한번 더 돌리는게 편할지도.. 밑에 코드는 이분탐색이다.

이제 어떤 $M$에 대해 모든 친구들이 위 조건을 통과한다면 $M$은 모두를 만족시키기에 가능한 값이 된다.

이런식으로 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;  
}