农夫约翰正在建造一个美丽的花园，在这个过程中需要移动大量的泥土。花园由N个花圃（1≤N≤100,000）组成，
第i个花圃最开始有Ai个泥土。 农夫约翰想要重新整理花园，使每个花圃最后有Bi个泥土。Ai和Bi都是0...10范围
内的整数。为了整理花园，Farmer John有几个选择：他可以购买一个单位的泥土，并将它放在他选择的花圃中，
用X单位的钱。 他可以从他选择的花圃上清除一块泥土，并用Y单位的钱运出去。他还可以用Z*|i-j|的花费将一单
位的泥土从花圃i运输到花圃j。请计算农民约翰完成他的绿化项目的最低总成本。
Input
第一行输入包含N，X，Y和Z（0≤X，Y≤10^8; 0≤Z≤1000）。
行i + 1包含整数Ai和Bi。
Output
请输出FJ需要花在园林绿化上的最低总成本。
Sample Input
4 100 200 1
1 4
2 3
3 2
4 0
Sample Output
210
转自:https://blog.csdn.net/lyd_7_29/article/details/78306987
位置可以发现只有两种：供给型（ai>bi），需求型（ai< bi）
由于ai,bi<=10，所以可以将一个位置拆成|ai-bi|个相同类型的位置，这样供给和需求都变成了1
此处只考虑供给位置
要么直接选择收购，要么选择移动
移动有两种：与前方的需求匹配，或者是当前不动与后方需求匹配
假设我们现在与前方需求匹配，那么肯定贪心选择一个费用最小的匹配，不会使得答案更差，使用一个需求堆来维护
但是，匹配后面的可能更优，所以我们要在供给堆里加入相应的值（为了以后撤销）
#include<set> #include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,b,a) for(int i=b;i>=a;i--) #define efo(i,v,u) for(int i=last[v],u=to[i];i;i=next[i],u=to[i]) #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)<(y)?(x):(y)) #define mset(a,x) memset(a,x,sizeof(a)) using namespace std; typedef long long ll; typedef double db; char ch; void read(int &n) { n=0;int p=1; for(ch=getchar();ch<‘0‘ || ch>‘9‘;ch=getchar()) if(ch==‘-‘) p=-1; for(;‘0‘<=ch && ch<=‘9‘;ch=getchar()) n=n*10+ch-‘0‘; n*=p; } int n; ll A,B,C; multiset<ll> s[2]; int main() { ll ans=0; read(n);scanf("%lld %lld %lld",&A,&B,&C); int x,y; fo(i,1,n) { read(x),read(y); fo(jy,1,x-y)//supply { ll co=B; if(!s[1].empty()) { ll t=*s[1].begin(); if(i*C+t<co) { co=i*C+t; s[1].erase(s[1].begin()); } } s[0].insert(-i*C-co); ans+=co; } fo(jy,1,y-x)//demand { ll co=A; if(!s[0].empty()) { ll t=*s[0].begin(); if(i*C+t<co) { co=i*C+t; s[0].erase(s[0].begin()); } } s[1].insert(-i*C-co); ans+=co; } } printf("%lld",ans); return 0; }
5519: [Usaco2016 Open]Landscaping
标签：
原文地址：https://www.cnblogs.com/cutemush/p/11684626.html