题解：P9113 [IOI 2009] Hiring

· · 题解

目前最优解。

Solution

考虑已选定工人，那么应该如何分配工资。设一份工资为 c 美元，则对于所有选定工人，会分到 c\times Q_i 美元，且 c \times Q_i \ge S_i，则 c \ge \frac{S_i}{Q_i}。所以 c = \max{\frac{S_i}{Q_i}} 时最优。

那么考虑如何选。我们先将所有工人按照 \frac{S_i}{Q_i} 从小到大排序，然后枚举这个 c 的位置。考虑每一次就是从一段前缀中贪心的选择 Q_i 最小的，且总和 \le \frac{W}{c}。这个直接用树状数组维护，然后在树状数组上二分即可。

记录最优的位置 w，以及最大个数 cnt。最后将前 w 个工人按照 Q_i 从小到大排序，输出前 cnt 个工人的编号即可。

实现的时候为了避免精度问题，用乘法代替除法即可。

时间复杂度 O(n\log_2 n)。

:::success[AC Code]

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 5e5 + 5, M = 2e4 + 5;
int n;
long long W; 
pair<pair<int, int>, int> a[N];
inline bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
    return a.x.x * b.x.y < a.x.y * b.x.x;
} 
inline bool cmp1(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
    return a.x.y < b.x.y;
} 
long long tr[M];
int tr1[M], cntt[M]; 
inline int lowbit(int x) {
    return x & -x;
}
inline void add(int x, int y) {
    cntt[x]++;
    for (int i = x; i < M; i += lowbit(i)) tr[i] += y, tr1[i] += 1;
}
int main() {
    //assert(freopen(".in", "r", stdin));
    //assert(freopen(".out", "w", stdout));
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> W;
    For(i, 1, n) cin >> a[i].x.x >> a[i].x.y;
    For(i, 1, n) a[i].y = i;
    sort(a + 1, a + n + 1, cmp);
    pair<int, pair<long long, int> > ans = mp(0, mp(0, 0));
    For(i, 1, n) {
        add(a[i].x.y, a[i].x.y);
        long long lim = W * a[i].x.y / a[i].x.x, sum = 0;
        int now = 0, cnt = 0;
        Dec(j, 15, 0) {
            if (now + (1 << j) >= M) continue;
            if (sum + tr[now + (1 << j)] <= lim) {
                now += (1 << j);
                sum += tr[now];
                cnt += tr1[now];
            }
        }
        long long yu = min(1ll * cntt[now + 1], (lim - sum) / (now + 1));
        cnt += yu;
        sum += yu * (now + 1);
        if (cnt > ans.x) ans = mp(cnt, mp(sum, i));
        else if (cnt == ans.x) {
            if (sum * a[i].x.x * a[ans.y.y].x.y < ans.y.x * a[ans.y.y].x.x * a[i].x.y) {
                ans = mp(cnt, mp(sum, i));
            }
        }
    }
    cout << ans.x << '\n';
    sort(a + 1, a + ans.y.y + 1, cmp1);
    For(i, 1, ans.x) cout << a[i].y << '\n';
    return 0;
}

:::