BOJ 2977 - 폭탄제조

BOJ 2977 - 폭탄제조

제한이 작아서 이분탐색을 잘 돌리면 시간내에 통과한다.

이 문제에서 자꾸 틀렸던 점은 남은 파트 개수가 $P$일 때, $LCM(S_M, S_V)$ 만큼 이득이 되는 방향으로 먼저 제거해주고 문제를 풀려했던 점인데 이건 반례가 있다.

그냥 이분탐색을 돌리며 완전탐색으로 큰것 개수를 $1$부터 늘려가는것이 정해이다.

void solve() {
   int n, m;
   cin >> n >> m;
   vector<array<int, 6>> P(n);
   for (int i = 0; i < n; i++) fv(P[i]);

   int l = 0, r = 1e5, ret = -1;
   while (l <= r) {
      int mid = (l + r) / 2;

      int need_money = 0;
      for (int i = 0; i < n; i++) {
         auto p = P[i];
         int need_part = p[0] * mid - p[1];
         if (need_part <= 0) continue;
         int buy_big = (need_part + p[4] - 1) / p[4];

         int tmp = buy_big * p[5];
         for (int big = 0; big <= buy_big - 1; big++) {
            int small = (need_part - big * p[4] + p[2] - 1) / p[2];
            assert(small >= 0);

            mina(tmp, big * p[5] + small * p[3]);
         }
         need_money += tmp;
         if (need_money > m) break;
      }

      if (need_money <= m) ret = mid, l = mid + 1;
      else r = mid - 1;
   }
   assert(~ret);
   cout << ret;
}