自动搬运

查看原文

来自洛谷，原作者为

	lytqwq ..

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

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

以下是正文

因为$A_i,B_i$很小，我们把每单位泥土分开看。

对于每单位泥土在第$i$个位置上，设处理该单位泥土花费$Vi$费用：

$V_i:$

1. 如果是少了泥土，可以花费$X$费用来解决，所以$V_i=X$，还可以向前面要泥土，要泥土一定向之前多泥土的地方要，要花费$Z|i-j|$费用，但之前的泥土我们已经考虑了它的贡献了，所以之前的泥土的贡献就要再减去（即之前的那个泥土多了，但是不需要处理了，后面少了的那个泥土直接要过来了），总的费用为$Z|i-j|-V_j$，所以$V_i=\min(X,Z|i-j|-V_j)$

2. 如果是多了泥土，可以花费$Y$费用来解决，所以$V_i=Y$。还可以往前面送泥土，送泥土一点向之前少泥土的地方送。同理，总的费用为$Z|i-j|-V_j$，所以$V_i=\min(Y,Z|i-j|-V_j)$

这样可以直接$O(100n^2)$计算了，可以解决此题的弱化版：https://www.luogu.com.cn/problem/P3049

但是对于此题，我们需要更快的方法：

拆开$V_i$的计算：

$V_i=\min(X,Z|i-j|-V_j)\space(i>j)$

$=\min(X,iZ-jZ-V_j)\space(i>j)$

$=\min(X,iZ+(-jZ-V_j))\space(i>j)$

所以，$V_i$的计算和前面的$j$有关的只有$(-jZ-V_j)$，要让当前的$V_i$最小，我们需要让$(-jZ-V_j)$最小。

为什么我们需要让$V_i$最小呢？为什么不把这个$j$留给后面的$V$呢？

前面的$(-jZ-V_j)$肯定是向后找最近的最好啊，越往后拖，$i$越大，$V_i$就有可能被$X$决定，还有可能出现距离更近的来更新。

开两个小根堆，一个存本来少了泥土的单位泥土的$(-jZ-V_j)$，可以用来更新现在多了泥土的地方。

另一个存本来多了泥土的单位泥土的$(-jZ-V_j)$，可以用来更新现在少了泥土的地方。

得到处理当前泥土的费用后把$(-iZ-V_i)$存进堆里，供后面的答案更新。

可以理解为后悔的贪心，把前面的费用给减去。

时间复杂度：$O(10nlog(10n))$

AC情况：https://www.luogu.com.cn/record/42168237

代码如下：

#include<bits/stdc++.h>
using namespace std;
const long long int N=100001;
long long int n,a[N],b[N],x,y,z;
long long int V[N];
long long int ans;
priority_queue<long long int,vector<long long int>,greater<long long int> > ovo,ovo2;
int main(){
   scanf("%lld%lld%lld%lld",&n,&x,&y,&z);
   for(long long int i=1;i<=n;i++){
   	scanf("%lld%lld",&a[i],&b[i]);
   	for(long long int o=1;o<=a[i]-b[i];o++){
   		V[i]=y;
   		if(!ovo.empty()){
   			V[i]=min(V[i],i*z+ovo.top());
   			ovo.pop();
   		}
   		ovo2.push(-V[i]-i*z);
   		ans+=V[i];
   	}
   	for(long long int o=1;o<=b[i]-a[i];o++){
   		V[i]=x;
   		if(!ovo2.empty()){
   			V[i]=min(V[i],i*z+ovo2.top());
   			ovo2.pop();
   		}
   		ovo.push(-V[i]-i*z);
   		ans+=V[i];
   	}
   }
   printf("%lld\n",ans);
}