不灭「不死鸟之尾」

gyyyyx · 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;
}