BOJ 5461 - 고용

BOJ 5461 - 고용

항상 정답이 되는 노동자들의 집합에서 어떤 노동자는 $Q_i \cdot k=S_i$ 임을 관찰한다.

따라서 $S_i / Q_i$ 순으로 오름차순 정렬해놓고 $k$를 증가시켜가며 현재 포함될 수 있는 노동자들을 모두 자료구조에 넣어서 관리한다.

그중 $Q_i$의 합이 작은 순서대로 $W$가 허용하는 만큼 뽑는다.

구현은 우선순위 큐에 $Q_i$ 들을 모두 넣고 들어가있는 $Q$의 값들의 합을 관리하며 $W$가 허용하지 못하는 $Q_i$ 들은 큰 순서대로 삭제를 한다.

그냥 삭제해버려도 되는 이유는 $k$는 게속 늘어나기 때문에 어차피 지금 삭제된게 나중에 쓰일일은 절대 없기 때문이다.

int N, W, S[500000], Q[500000];
vi idx;

void solve() {
   cin >> N >> W;
   idx.resize(N);
   iota(all(idx), 0);
   for (int i = 0; i < N; i++) cin >> S[i] >> Q[i];
   sort(all(idx), [&](int i, int j) { return S[i] * Q[j] < S[j] * Q[i]; });

   int qsum = 0;
   priority_queue<pi> pq;
   int ans_cnt = -1;
   double ans_cost = 2e15;
   for (int _i = 0; _i < N; _i++) {
      int i = idx[_i];
      qsum += Q[i];
      pq.push({Q[i], i});
      while (sz(pq) && S[i] * qsum > W * Q[i]) {
         qsum -= pq.top().fi;
         pq.pop();
      }
      if (sz(pq) > ans_cnt || sz(pq) == ans_cnt && ans_cost * Q[i] > S[i] * qsum) {
         ans_cnt = sz(pq);
         ans_cost = 1.0 * qsum * S[i] / Q[i];
      }
   }
   cout << ans_cnt << endl;
   qsum = 0;
   while (sz(pq))pq.pop();
   for (int _i = 0; _i < N; _i++) {
      int i = idx[_i];
      double k = S[i] / Q[i];
      qsum += Q[i];
      pq.push({Q[i], i});
      while (sz(pq) && S[i] * qsum > W * Q[i]) {
         qsum -= pq.top().fi;
         pq.pop();
      }
      if (sz(pq) == ans_cnt && abs(1.0 * qsum * S[i] / Q[i] - ans_cost) < 1e-5) {
         while (sz(pq)) {
            cout << pq.top().se + 1 << endl;
            pq.pop();
         }
         return;
      }
   }
}