题意

农夫约翰正在建造一个美丽的花园，在这个过程中需要移动大量的泥土。花园由N个花圃（1≤N≤100,000）组成， 第i个花圃最开始有Ai个泥土。 农夫约翰想要重新整理花园，使每个花圃最后有Bi个泥土。Ai和Bi都是0…10范围 内的整数。为了整理花园，Farmer John有几个选择：他可以购买一个单位的泥土，并将它放在他选择的花圃中， 用X单位的钱。 他可以从他选择的花圃上清除一块泥土，并用Y单位的钱运出去。他还可以用Z*|i-j|的花费将一单 位的泥土从花圃i运输到花圃j。请计算农民约翰完成他的绿化项目的最低总成本。 0≤X，Y≤10^8; 0≤Z≤1000

分析

显然如果数据小的话我们可以用费用流或上下界费用流来实现。

假设i>j，那么|i-j|*z可以拆成i*z-j*z。 那么我们可以从前往后做： 维护两个堆need和noneed，need内维护的是需要补上的树，noneed内维护的是多出来的树。 若要将位置i的树运掉，其费用为v，然后我们就在noneed中插入-i*z-v； 若要在位置i加入一棵树，其费用为v，然后我们就在need中插入-i*z-v； 然后如果当前位置的树有多，那么就在need中找一个最小的值w，那么其费用就是i*z-w；设其费用为v，然后在noneed中插入-i*z-v即可。 为什么是对的呢？因为把式子展开后就发现这其实是这次的代价减去之前的代价。 当前位置的树不足的情况同理。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #define N 100005 #define LL long long using namespace std; int n,x,y,z,val[N]; priority_queue<LL> need,noneed; int main() { scanf("%d%d%d%d",&n,&x,&y,&z); for (int i=1;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); val[i]=x-y; } LL ans=0; for (int i=1;i<=n;i++) if (val[i]>0) { for (int j=1;j<=val[i];j++) if (need.empty()) ans+=y,noneed.push(i*z+y); else { int w=-need.top(); if (i*z+w<y) ans+=i*z+w,need.pop(),noneed.push(i*z*2+w); else ans+=y,noneed.push(i*z+y); } } else { for (int j=1;j<=-val[i];j++) if (noneed.empty()) ans+=x,need.push(i*z+x); else { int w=-noneed.top(); if (i*z+w<x) ans+=i*z+w,noneed.pop(),need.push(i*z*2+w); else ans+=x,need.push(i*z+x); } } printf("%lld",ans); return 0; }