自动搬运

查看原文

来自洛谷，原作者为

	happy_dengziyue GD OIer|路漫漫其修远兮，吾将上下而求索

搬运于2025-08-24 23:08:42，当前版本为作者最后更新于2025-02-24 20:05:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

1 思路

我们不必限制柱子的高度必须是整数，也不必限制必须是非负数。因为调整法可以证明如果柱子的高度不是非负整数就一定不优。

首先考虑动态规划。设 $dp_{i,j}$ 为：只考虑前 $i$ 柱并且第 $i$ 柱高度必须是 $j$ 时的最小代价。

边界情况是 $dp_{0,j}=0$。可以容易地写出转移：

答案则为 $dp_N$ 的最小值。

直接计算这个式子显然是无法通过的。但是我们发现 $dp_i$ 一定是个下凸函数：因为 $dp_{0,j}=0$，而之后的操作也不会破坏下凸的性质。

再分析这个式子。可以化为对 $dp_i$ 的如下两个修改操作：

第一个操作实际上是将常函数段左侧往左平移 $H$，常函数段右侧往右平移 $H$，类似“拉扯”。第二个操作实际上是加上一个简单的 V 形函数。

可以考虑用两个优先队列分别维护常函数段左侧和常函数段右侧的折点，同时维护常函数段的值。

第一个操作只需要打个标记。第二个操作要分讨 V 形函数的顶点在常函数段横坐标范围里还是两侧，并修改常函数段横坐标范围；如果是两侧还需还需要计算常函数段的值的变化。

时间复杂度 $\Theta(N\log N)$。

2 代码与记录

#include<bits/stdc++.h>
using namespace std;
#define max_n 200000
#define inf ((long long)2e9)
int n;
long long lim;
long long a[max_n+2];
priority_queue<long long>ql;
priority_queue<long long,vector<long long>,greater<long long>>qr;
long long low=0;
long long tagl=0,tagr=0;
int main(){
	#ifdef dzy
	freopen("P11598_1.in","r",stdin);
	freopen("P11598_1.out","w",stdout);
	#endif
	scanf("%d%lld",&n,&lim);
	for(int i=1;i<=n;++i)scanf("%lld",a+i);
	ql.push(-1); qr.push(inf); low=0;
	for(int i=1;i<=n;++i){
		tagl-=lim; tagr+=lim;
		long long l=ql.top()+tagl,r=qr.top()+tagr;
//		printf("l=%lld r=%lld low=%lld\n",l,r,low);
		if(l<=a[i]&&a[i]<=r){ql.push(a[i]-tagl); qr.push(a[i]-tagr);}
		else if(a[i]<l){
			low+=l-a[i];
			ql.push(a[i]-tagl); ql.push(a[i]-tagl);
			qr.push(ql.top()+tagl-tagr); ql.pop();
		}
		else{
			low+=a[i]-r;
			qr.push(a[i]-tagr); qr.push(a[i]-tagr);
			ql.push(qr.top()+tagr-tagl); qr.pop();
		}
	}
	printf("%lld\n",low);
	return 0;
}

记录传送门

By dengziyue