自动搬运

查看原文

来自洛谷，原作者为

	gyyyyx Soft亲爹|折戟溺秽，溅者必卒|正处于体内充满不纯氢气的状态

搬运于2025-08-24 22:46:22，当前版本为作者最后更新于2023-04-10 19:14:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题面

首先我们思考一段长为 $len$ 的连续空位停一辆车的最小时间。

如果这辆车停在两侧，那最小时间显然是 $w_i-(len-1)\max(l_i,r_i)$。

不妨设 $l_i\leq r_i$，那停在两侧的最优解是停在最左边，时间为 $w_i-(len-1)r_i$。

如果这辆车右移 $x$ 个车位，那时间将会变成 $w_i-x\cdot l_i-(len-1-x)r_i=w_i-(len-1)r_i+x(r_i-l_i)$。

因为 $l_i\leq r_i,x>0$，所以 $x(r_i-l_i)\geq 0$，那这样时间肯定不会减少，看得出来一段长度为 $len$ 的连续空位停一辆车的最小时间为 $w_i-(len-1)\max(l_i,r_i)$。

那是否有可能这样子贪心的停在两侧会影响到后面，或者说有没有情况使得某一辆车不停在两侧能让时间减少。

我们发现当 $w,l,r$ 不变时，$len$ 越大，时间越小。

而刚好，停在两侧的情况能保证一直都只有一段连续车位，长度 $len$ 从 $n$ 开始不断减一，使得 $len$ 一直是最大的。

那就好办了，一直贪心取下去就行。

代码：

#include<bits/stdc++.h>
#define LL long long
#define N 100005
using namespace std;
int n;LL W[N],L[N],R[N],ans;
int main(){
	scanf("%d",&n);
	for(int i(1);i<=n;++i) scanf("%lld",&W[i]);
	for(int i(1);i<=n;++i) scanf("%lld",&L[i]);
	for(int i(1);i<=n;++i) scanf("%lld",&R[i]);
	for(int i(1);i<=n;++i) ans+=W[i]-(n-i)*max(L[i],R[i]);
	printf("%lld\n",ans);
	return 0;
}