自动搬运

查看原文

来自洛谷，原作者为

	foreverlasting 果然，失去别人远比自己离去更加令人恐惧。

搬运于2025-08-24 21:58:23，当前版本为作者最后更新于2022-08-30 21:10:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

写这篇题解的主要目的是好好普及下 $\mathrm{slope\ trick}$ 的答案构造，因为通过观察网上题解，疑似都没说清楚为啥是对的，甚至克拉丽丝特判了数据点才过的...所以俺写了这篇题解。

题意：给出一个序列 $a$ 和三个正整数 $mx,p,q$，要求构造一个序列 $b$，使得 $\sum_{i=1}^n |a_i-b_i|$ 最小的同时，满足 $b_i\in [b_{i+1}-q,b_{i+1}-p]$，且必须满足 $1\leq b_i\leq mx$。

题解：一道有范围限制且要构造方案的 $\mathrm{slope\ trick}$ 题。

首先注意到 $1,p+1,2p+1,\cdots,(n-1)p+1$ 一定是一组解，题目有保证，这也就说明了一定有解。

考虑一个暴力 $\mathrm{dp}$，设 $f_{i,j}$ 表示当前计算到第 $i$ 个数，当前选择的 $b_i$ 是 $j$ 的最小贡献，显然有转移

好像和平时遇到的 $\mathrm{slope\ trick}$ 都没有区别，其实是有的。平日里遇到的，$j$ 的范围都是 $(-\infty,\infty)$，但这道题并不是。在这道题中，特意限定了 $j$ 的范围是 $[1,mx]$。这意味着什么呢？

我们继续考虑 $\mathrm{slope\ trick}$ 的那一套逻辑，把 $f_{i,j}$ 看成是 $j$ 的函数，此刻取 $\min$ 等价于凸包平移加底部拉长的一个过程，但是由于 $j$ 有限制，这意味在算完第一个数后，凸包在 $[mx+1,\infty)\cup (-\infty,0]$ 的部分的值都该是无意义，为了方便起见，我们设这个值为 $\infty$。

于是，每一次平移之后，凸包非 $\infty$ 的部分总是被限制。很容易地，我们知道对第 $i$ 个凸包而言，这个限制的范围是 $[(i-1)\cdot p+1,mx]$，也即 $b_i\in [(i-1)\cdot p+1,mx]$。这意味着这个凸包在平移拉伸后，还多了个截取的过程。而加入一个 $|x-a_i|$，这都是 $\mathrm{slope\ trick}$ 的基础套路，用两个懒标记和堆来维护分界点即可。而由于新增的截取过程，这让我们在往堆里加分界点的时候，可以与 $mx$ 取 $\min$。

于是就剩下构造答案了，首先得知道三个性质。

性质一：我们在维护这个凸包的时候，除了维护每个斜率变化的分界点外，还维护了最低点的纵坐标值。于是在最后的凸包里，我们知道 $b_n$ 一定处于凸包的最小值所在的横坐标区间中。但要注意到，对此时的凸包而言，最低点不一定是斜率为零的点了，这是由于多了截取的存在。

性质二：我们要清晰知道一件事，在 $\mathrm{slope\ trick}$ 中，第 $i$ 个凸包一定是前 $i$ 个数构成的答案凸包。这是什么概念呢？这意味着在这个凸包上的所有值一定是合法的，也即一定有一个对应的解。这个利用归纳法是容易证明，也不再赘述。既然凸包上的值一定合法，也就意味着无论最后一个数如何取，只要是在凸包上，意味着一定有一组解来对应它。

性质三：我们要知道一个显然的贪心性质，在前面的凸包中，如果每次 $b_i$ 都能取到凸包最低点而且与后面不冲突的话，那就是一定不劣的。这个是容易感受出来的，若斜率为零的那一段能够恒久存在，那我们一直选择这一段是永远不劣的。

有了以上的三个性质，我们就可以构造答案了。

性质三意味着在初步构造中，我们可以贪心地让每个 $b_i$ 成为当前凸包的最低点。然后利用性质二，我们知道 $b_n$ 一定是合法的，所以进行倒推，使得每个 $b_i\in [b_{i+1}-q,b_{i+1}-p]$。那么如何倒推呢？若初步构造的 $b_i$ 已经在这个区间了，那就皆大欢喜。若 $b_i<b_{i+1}-q$，由于一定存在一组解，利用贪心的性质，此刻让 $b_i\leftarrow b_{i+1}-q$ 一定最优，原因也很简单，因为初步构造时 $b_i$ 是凸包的最低点，而此时 $b_i$ 离 $b_{i+1}-q$ 最近，那么取这个端点一定最优。大于右端点同理。

于是就顺利构造出一组答案了，且一定是最小的(因为 $b_n$ 一定在最终凸包上)。

代码实现上，我们不一定要真的对维护分界点的堆进行即时的截取。可以类似懒标记那样，对每个初步构造的 $b_i$ 先与 $mx$ 取 $\min$，再与 $(i-1)\cdot p+1$ 取 $\max$ 即可。这样代码会比较好写。

同时在这里也给出了所有 $\mathrm{slope\ trick}$ 题的答案构造方式。

//2022.8.30 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=5e5+10;
namespace MAIN {
	int n,mx,p,q;
	int a[N];
	LL b[N];
	priority_queue<LL> L;
	priority_queue<LL,vector<LL>,greater<>> R;
	inline void MAIN(const int &Case) {
		n=read(),mx=read(),p=read(),q=read();
		for(int i=1;i<=n;i++)a[i]=read();
		LL tagl=0,tagr=0;
		L.push(a[1]),R.push(a[1]),b[1]=a[1];
		for(int i=2;i<=n;i++){
			tagl+=p,tagr+=q;
			LL l=L.top()+tagl,r=R.top()+tagr;
			if(a[i]<l)L.pop(),R.push(l-tagr),L.push(a[i]-tagl),L.push(a[i]-tagl);
			else if(a[i]>r)R.pop(),L.push(r-tagl),R.push(a[i]-tagr),R.push(a[i]-tagr);
			else L.push(a[i]-tagl),R.push(a[i]-tagr);
			LL t=L.top()+tagl;
			b[i]=min((LL)mx,max((LL)p*(i-1)+1,t));
		}
		for(int i=n-1;i>=1;i--){
			if(b[i]>b[i+1]-p)b[i]=b[i+1]-p;
			if(b[i]<b[i+1]-q)b[i]=b[i+1]-q;
		}
		LL ans=0;
		for(int i=1;i<=n;i++)ans+=abs(a[i]-b[i]);
		printf("%lld\n",ans);
	}
}