自动搬运

查看原文

来自洛谷，原作者为

	ayaka 周而复始的7days。

搬运于2025-08-24 23:14:56，当前版本为作者最后更新于2025-07-03 13:27:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

首先我们明白，未被看到的体育场完全可以当作最劣情况考虑。那么最劣的情况奖金数量和对方的技能等级顺序排列。遂我们可以构造出看完前 $k$ 个球场后最劣的情况：

• 对于前 $k$ 个球场，$p$ 和 $b$ 不变；
• 对于后 $n-k$ 个球场，$p$ 和 $b$ 皆顺序排序。

随后考虑我方如何获得最大奖金。枚举我方能力小的到能力大的，用优先队列存储第 $i$ 名球员可以成功获得奖金的体育场，把第 $i$ 名球员安放到他打得过且奖金最高的场地即可。由于后面的球员一定也能前往前面的球员可以前往的体育场，因此正确性得以证明。

具体做法就是二分至多能看完的体育场数量 $k$，然后对于当前的 $k$ 暴力构造出最劣的情况跑即可。构造情况和给球员找场地的复杂度为 $O(n \log n)$，总复杂度 $O(n \log^2 n)$。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, p[500005], a[500005], b[500005], x[500005], y[500005], l, r, sum, ans;
struct node {
	int p, b;
} c[500005];
bool cmp(node x, node y) {
	return x.b < y.b;
}
priority_queue<int, vector<int>, less<int>> q;//较大的元素会被优先取出 
bool check(int k) {
	int res = 0;
	while (!q.empty()) q.pop();
	for (int i = 1; i <= n; i++) {
		x[i] = p[i];
		y[i] = b[i];
	}
	sort(x + k + 1, x + n + 1);
	sort(y + k + 1, y + n + 1);
	for (int i = 1; i <= n; i++) {
		c[i] = {x[i], y[i]};
	}
	sort(c + 1, c + n + 1, cmp);
	for (int i = 1, j = 1; i <= n; i++) {
		while (c[j].b < a[i] && j != n + 1) {
			q.push(c[j++].p);//把所有打得过的放入优先队列 
		}
		if (!q.empty()) {
			res += q.top();
			q.pop();
		}//若没有可放的就让这个球员凑数就好了，因此不用计算贡献 
	}
	if (sum < res * 2) return 1;
	return 0;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> p[i], sum += p[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	if (!check(n)) {
		cout << "-1";
		return 0;
	}//特判无法获胜的情况 
	l = 0, r = n, ans = n;
	while (l <= r) {
		int mid = ((l + r) >> 1);
		if (check(mid)) {
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << ans;
	return 0;
}