自动搬运

查看原文

来自洛谷，原作者为

	acb437 AD ASTRA PER ASPERA

搬运于2025-08-24 22:36:11，当前版本为作者最后更新于2024-11-19 22:11:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题解：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$。

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

• 两个凸函数相加还是凸函数，并且对于分段一次凸函数而言，它们的和的函数的分段点集合为两个函数分段点集合的并集，即设分段一次函数 $F(i)$ 和 $G(i)$ 的分段点集合分别为 $S_F$ 和 $S_G$，则它们的和 $H(i)$ 的分段点集合 $S_H$ 为 $S_F \cup S_G$。
• 凸函数加一次函数还是凸函数。

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

• 是连续的。
• 是分段一次函数。
• 是凸函数或凹函数。

操作

• 相加：直接把最左边的一次函数相加，分段点集合合并。
• 函数最值：用大根堆维护斜率为 $0$ 的段左侧的分段点，即斜率为正数（凹函数为负数）时的分段点，用小根堆维护右侧的分段点，即斜率为负数（凹函数为正数）时的分段点。所以大根堆中元素个数为最左边一段一次函数的斜率的绝对值，并且如果一个凸函数最左边的一次函数斜率不为正，那大根堆就是空的，小根堆以及凹函数的情况同理。如果一个点 $a$ 的左侧斜率为 $x(x>0)$，右侧斜率为 $-y(y>0)$，那么大根堆存储 $x$ 个 $a$，小根堆存储 $y$ 个 $a$ 即可，凹函数同理。

更多的操作可以参考

(https://www.cnblogs.com/cccomfy/p/17743031.html)，有了这两条操作，我们已经可以做这道题（以及许多 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)$ 最小，则有：

1. $a_i\ge t$ 时，显然贡献可以直接取 $H(a_i)=0$ 这个值，不需要增加答案，在 $a_i$ 这个点右侧的函数斜率变为 $1$，于是只需要保留 $1$ 个 $a_i$。
2. $a_i<t$ 时，设 $t$ 左侧的第一个分段点为 $p$（插入后），那么对于 $p\le y\le t$，$F(y)$ 的值相等，即 $F(x)$ 函数的这一段斜率为 $0$，所以 $F(x)$ 的最小值既是 $dp_{i-1,p}+\lvert a_i-p\rvert$，也是 $dp_{i-1,t} + \rvert a_i-t\rvert$，由于我们先前维护的是 $G(x)$ 的最小值，即 $dp_{i-1,t}$，所以我们需要加上的贡献为 $\lvert a_i-t\rvert$，但是这个值（指 $F(x)$ 的最小值）的意义是 $dp_{i,p}$ 的意义，即 $a_i$ 变为 $p$ 而不是变为 $t$。

代码

#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 详解。