5461번: 고용

https://www.acmicpc.net/problem/5461


$O(n\lg n)$

먼저, 노동자들을 s/q를 기준으로 오름차순 정렬한다.
그러면 i번 노동자를 고용할 수 있을 경우 1...i-1번 노동자도 고용할 수 있다.
고용 가능한 노동자 후보가 있을 때 q가 작은 순서대로 고용할 때 가장 많은 노동자를 고용할 수 있다.
Ai를 1...i번 노동자 중 q가 작은 순서대로 최대한 많이 고용한 노동자의 집합이라 하자.
그러면 Ai에서 고용되지 않는 노동자는 Ai+1에서 역시 고용되지 못한다. 이는 귀류법으로 간단히 증명된다.
이러한 성질을 이용하여 노동자 집합을 q를 기준으로 하는 우선순위 큐를 통해 관리할 수 있다.

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int MXN = 5e5;
int n, q[MXN + 1], sz, ti;
pair<double, int> p[MXN + 1];
pair<int, int> r[MXN + 1];
long long w, s;
double tw;
priority_queue<pair<int, int> > pq;
int main() {
    scanf("%d%lld", &n, &w);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d%d", &x, q + i);
        p[i] = { x*1.0 / q[i],i };
    }
    sort(p + 1, p + 1 + n);
    for (int i = 1; i <= n; i++) {
        s += q[p[i].second];
        pq.push(r[i] = { q[p[i].second],p[i].second });
        while (s*p[i].first > w) s -= pq.top().first, pq.pop();
        if (pq.size() > sz || pq.size() == sz&&s*p[i].first < tw) {
            sz = pq.size();
            tw = s*p[i].first;
            ti = i;
        }
    }
    sort(r + 1, r + 1 + ti);
    printf("%d\n", sz);
    for (int i = 1; i <= sz; i++) printf("%d\n", r[i].second);
    return 0;
}