P9113 [IOI2009] Hiring

· · 题解

P9113 [IOI2009] Hiring

考虑选择一些工人后怎么分配工资。根据监管局的要求，所有人的工资 W_i 和其能力值的比值 Q_i 相同。设 c = \frac {W_i} {Q_i}，则对于任意选择的工人 i，Q_ic \geq S_i。由此可知 c\geq \max\frac {S_i}{Q_i}。为了让总工资最小，c = \max \frac {S_i} {Q_i}。我们将该比值最小的工人称为 “基准工人”。

将所有工人按 \frac {S_i} {Q_i} 从大到小排序，如果我们钦定基准工人为 i，则只能选择编号在 i 之后的工人。设选择的集合为 T，总工资即 \frac {S_i\sum_{j \in T} Q_j} {Q_i}。S_i 和 Q_i 都是定值，所以为了选择尽可能多的工人，按 Q_j 从小到大选择。

因此，问题转化为：每次插入一个数 Q_i，然后查询最多选出多少个 Q_j，使得它们的和不超过 \frac {WQ_i} {S_i}。插入用线段树或树状数组维护，查询用线段树二分或树状数组二分即可。注意两个相同的 Q_j 需要插入不同的位置，或者在查询时特判（因为可能没取完相同的 Q_j）。

输出方案也是容易的。记录 \max |T| 和工资以及对应的 i，选择 i\sim n 中 Q_j 最小的 |T| 个工人。

时间复杂度 \mathcal{O}(n\log n)。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool Mbe;
constexpr int N = 5e5 + 5;

ll W;
int n, b[N], buc[N];
struct worker {
  int s, q, id;
  bool operator < (const worker &z) const {
    return s * z.q > q * z.s;
  }
} w[N];

ll c[N];
int d[N];
void add(int x, int v) {
  while(x <= n) c[x] += v, d[x]++, x += x & -x;
}
pair<ll, int> query(ll lim) {
  ll sc = 0, sd = 0, p = 0;
  for(int i = 18; ~i; i--) {
    int np = p + (1 << i);
    if(np > n) continue;
    if(sc + c[np] > lim) continue;
    sc += c[p = np], sd += d[p];
  }
  return make_pair(sc, sd);
}

bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin); 
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> W;
  for(int i = 1; i <= n; i++) {
    cin >> w[i].s >> w[i].q, buc[w[i].q]++, w[i].id = i;
  }
  sort(w + 1, w + n + 1);
  for(int i = 1; i < N; i++) buc[i] += buc[i - 1];
  int pos = 0, ans = -1;
  ll nu, de;
  for(int i = n; i; i--) {
    int p = buc[w[i].q]--;
    add(p, w[i].q);
    auto t = query(W * w[i].q / w[i].s);
    ll sq = t.first, cnt = t.second;
    ll nu1 = w[i].s * sq, de1 = w[i].q;
    if(cnt > ans || cnt == ans && nu1 * de < nu * de1) {
      ans = cnt, pos = i, nu = nu1, de = de1;
    }
  }
  sort(w + pos, w + n + 1, [&](auto x, auto y) {
    return x.q < y.q;
  });
  cout << ans << "\n";
  for(int i = 0; i < ans; i++) cout << w[pos + i].id << "\n";
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}