题解 P2748 【[USACO16OPEN]Landscaping P】

· · 题解

因为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);
}