P8118 Mystery 题解

· · 题解

题解：P8118 Mystery

前言

朋友在 PJudge 上做题时看到了这道题的原题（或者这是那道题的原题？）并让我看一看，当时我的第一反应就是：这题绝对是贪心。思考良久，他却告诉我这道题有更加优雅的解法，而且这个 trick 我们都见过，它就是：Slope Trick。

前置知识：Slope Trick

介绍

这个 trick 是一种用来维护函数的方法，简单来说，它一般包括存储分段一次凸 / 凹函数最左边或最右边一段的函数和用数据结构（一般是堆）来维护分段一次凸 / 凹函数的分段点：如果一个分段点 x 右侧的一次函数的斜率比左侧的一次函数的斜率多 / 少 k（在这个 trick 中，我们要求 k 是整数），就在堆中插入 k 个 x。

举例而言，对于一个分段一次凸函数 F(x)：

F(x)=\left\{ \begin{array}{rcl} 2x & x < 0\\ 0 & 0\le x\le 9\\ -4x + 36 & 9 < x \end{array} \right.

我们用向堆中插入 2 个 0 和 4 个 9，表示斜率在 0 的位置变小了 2，在 9 的位置变小了 4。

乍一看似乎没有什么作用，它的能力其实建立在分段一次凸 / 凹函数的优秀性质上（以下全部用凸函数，凹函数具有同样或类似的性质）:

这样我们就可以发现 Slope Trick 的一些作用了，比如说，它维护的正是分段一次函数的分段点，而且这么维护斜率的变化对于分段一次凸函数之间的相加十分方便。所以被它用来维护的函数一般有一下要求：

更多的操作可以参考 @CCComfy 大佬的 这篇博客，有了这两条操作，我们已经可以做这道题（以及许多 Slope Trick 的题）了。

思路简述

这道题其实和 Slope Trick 的一道经典题（不算本题就有 5 倍经验）十分类似，我们将每个 a_i 变为 a_i - i\times k，就把这道题转化为了这道经典题：给定一个序列 a，你可以对序列中任意一个数执行 +1 或 -1 操作，使得序列 a 变为单调不降的，问最少需要几次操作。

接下来分析这道经典题的做法：

考虑 dp，设 dp_{i,j} 表示枚举到第 i 位，将 a_i 变为 j 并且前 i 位单调不降的最小操作次数，则有转移方程 dp_{i,j}=\min_{k\le j}dp_{i-1,k}+\lvert a_i-j\rvert，显然可以进行前缀和优化，令 dp_{i,j}=\min(dp_{i,j-1},dp_{i-1,j}+\lvert a_i-j\rvert) 即可。

由于取了前缀 \min，dp 方程显然为一个凹函数，设 F(x) 为 dp_i，G(x) 为 dp_{i-1}，绝对值函数 H(x)=\lvert a_i-x\rvert，则 F(x)=G(x)+H(x)，H(x) 和 G(x) 都是凹函数，F(x) 也为凹函数，由于维护前缀 \min 即可，我们只需要用大根堆维护斜率为 0 的段左边斜率为负数的分段一次函数即可，不需要维护最左侧一次函数的 k 和 b 以及右侧的函数。加上 H(x) 就相当于在大根堆中插入 2 个 a_i（H(x) 的斜率从 -1 变为 1，函数相加直接合并分段点集合）。

插入之后，由于 H(x) 开头的斜率为 -1，大根堆中的元素只会增加 1 个，于是需要弹出堆顶，因为此时的堆顶位置右侧的函数斜率已经变为了 1，而不是 0。贡献如何计算需要分类讨论，设原本（插入前）大根堆的堆顶为 t，即 x 取到 t 时，G(x) 最小，则有：

代码

#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
int n, k, t;ll ans, a[N];
priority_queue <ll> heap;

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1;i <= n;i++)scanf("%lld", &a[i]), a[i] -= 1ll * i * k;
    scanf("%d", &t);
    for(int i = 1;i <= n;i++)
    {
        heap.push(a[i]);
        if(a[i] < heap.top())
            ans += heap.top() - a[i], heap.pop(), heap.push(a[i]);
        if(!t)printf("%lld\n", ans);
    }
    if(t)printf("%lld\n", ans);
    return 0;
}

鸣谢：CCComfy 大佬的 Slope Trick 详解。