P6877 题解

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

希望能帮助到大家！