自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:45:27，当前版本为作者最后更新于2023-03-08 10:42:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}