题解：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)

。

AC Code

CPP

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

题解：P9113 [IOI 2009] Hiring

文章操作

Solution

相关推荐

评论

题解：P9113 [IOI 2009] Hiring