---
tags: IOI
---
# IOI2009 Day1-2 雇用 (Hiring)

## 問題

https://www.ioi-jp.org/ioi/2009/problems/day1/Hiring_jp.pdf
https://oj.uz/problem/view/IOI09_hiring

$N$ 人の労働者がいて、 $i$ 番目の労働者は雇うのに最低 $S_i$ ドル必要で、労働水準は $Q_i$ である。
あなたは $W$ ドル持っていて、できるだけ多くの労働者を雇いたい。
ただし、法律によって、労働者には労働水準に比例する賃金を支払う必要がある。
雇える人数の最大値と、そのときの支払う賃金の合計が最小になる雇い方を求めよ。

$N ≤ 500000$

## 考察

雇う人数を増やすと、必要なお金は単調増加する。

(支払う賃金) $= \max(\frac{S_i}{Q_i})\times\mathrm{sum}(Q_i)$

であるから、 $\frac{S_i}{Q_i}$ でソートすると良さそう。

$\max(\frac{S_i}{Q_i})$ を固定すると、その中で $Q_i$ が小さい順に $W$ を超えそうになるまで選んでいけば良い。

よって、 $\frac{S_i}{Q_i}$ の昇順に priority_queue に入れて、 $W$ を超えたら取り出していけば良い。

復元いる？

愚直に保存すると $O(N^2)$
これは変化を list に保存すると $O(N)$

## 実装

https://oj.uz/submission/220795

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
#define rep(b) for(int i = 0; i < b; i++)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)
 
 
ll cnt;
vector<ll> hist;
struct Q{
    priority_queue<pll> q;
    ll sum = 0;
    void push(ll val, ll index){
        cnt++;
        sum += val;
        hist.push_back(index);
        q.emplace(val, index);
    }
    void pop(){
        cnt--;
        sum -= q.top().first;
        hist.push_back(q.top().second);
        q.pop();
    }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n, w;
    cin >> n >> w;
    vector<pll> a(n);
    each(i, a) cin >> i.first >> i.second;
    vector<ll> b(n);
    iota(all(b), 0);
    sort(all(b), [&](ll x, ll y){ return a[x].first * a[y].second < a[x].second * a[y].first; });
    ld rate = 0, cost = 0;
    ll ans = 0;
    Q q;
    vector<bool> hire(n);
    auto update = [&](ld cost_) -> void {
        if(ans > cnt) return;
        if(ans == cnt && cost <= cost_) return;
        ans = cnt;
        cost = cost_;
        each(i, hist) hire[i] = !hire[i];
        hist.clear();
    };
    each(i, b){
        auto [sal, qual] = a[i];
        rate = ld(sal) / qual;
        q.push(qual, i);
        while(q.sum * rate > w) q.pop();
        update(q.sum * rate);
    }
    cout << ans << '\n';
    rep(n) if(hire[i]) cout << i + 1 << '\n';
}