自动搬运

查看原文

来自洛谷，原作者为

	liangbowen 不能再摆了，，，

搬运于2025-08-24 22:24:50，当前版本为作者最后更新于2022-12-18 22:54:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

题目传送门！

更好的阅读体验？

贪心。内容抄自某校课件。

思路

部分分

这个随便搞都可以，可以二分答案然后建边然后跑二分图最大匹配。

正解

考虑贪心。这里有一个很容易猜到或想到的结论：

将 $a$ 与 $b$ 从小到大排序，直接按位配对（$a_i$ 配 $b_i$），就是最优解。

设排序后的数组是 $a ^ \prime$ 与 $b ^ \prime$，也就是说我们要找到 $\min k$ 满足 $\forall a_i^\prime - b_i^\prime \le k$。那么很显然，答案就是 $\max\limits_{i = 1}^n (a_i^\prime - b_i^\prime)$。

然后问题就在于，迅速的维护这个东西了。

这个很简单：维护 $(a_i - b_i)$ 的前缀 $\max$ 与 $(a_{i + 1} - b_i)$ 的后缀 $\max$，然后挨个查询即可。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
struct Monkey {int val, id;} a[N];
bool cmp(Monkey p, Monkey q) {return p.val < q.val;}
int b[N], pre[N], suf[N], ans[N]; //pre[i]记录ai-bi前缀mx，suf[i]记录ai+1 - bi后缀mx
int main()
{
	ios::sync_with_stdio(false);
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n + 1; i++) scanf("%d", &a[i].val), a[i].id = i;
	for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
	sort(a + 1, a + n + 2, cmp), sort(b + 1, b + n + 1);
	for (int i = 1; i <= n; i++) pre[i] = max(pre[i - 1], a[i].val - b[i]);
	for (int i = n; i; i--) suf[i] = max(suf[i + 1], a[i + 1].val - b[i]);
	for (int i = 1; i <= n + 1; i++) ans[a[i].id] = max(pre[i - 1], suf[i]);
	for (int i = 1; i <= n + 1; i++) printf("%d ", max(ans[i], 0));
	return 0;
}

希望能帮助到大家！