题解 P2517 【[HAOI2010]订货】

这个奇妙的想法发源于一位不知道费用流的蒟蒻与一道费用流大火题的碰撞之中,我惊讶地发现,用贪心乱搞也能达到0ms,且代码量大大小于费用流. **step1:**对于一个日子,它可以从之前任意一天购买,并且还收到容量的限制。一个很自然 的想法就是贪心,每次选择能够选择的日期中价格最小的天来购买。 **step2:**所以我们考虑按照购买日期维护一个单调队列,单调队列的元素是价格递增的。每 次能够选取的价格最小的日期就对应着单调队列的队首元素。从队首购买水会导致队列 中所有元素的可用容量都变小。接下来我们只需要把队列中所有元素的可用容量全部减 去当前使用数量。 从这里可以顺便看出单调队列中的元素的容量是单调递增的,每次我们贪心地取队 首元素,如果发现队首元素容量为0就把它删除,每一天过完后就暴力把队列中所有元 素的费用增加。 每次修改复杂度是O(n)的,共购买n天,复杂度O(n 2 ) **step3:**然后我们发现单调队列需要支持的操作是:整体加减、单点插入删除。我们可以维护一 个lazy标记,这样就可以把修改的复杂度降到O(1)。总复杂度O(n) ```cpp #include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define ll long long #define re register #define il inline #define fp(i,a,b) for(re int i=a;i<=b;i++) #define fq(i,a,b) for(re int i=a;i>=b;i--) using namespace std; const int N=10005; il ll gi() { re ll x=0; re int t=1; re char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t; } ll d[N],p[N],q[N],w[N];//q里存位置,位置的价格单调递增 int main() { int n=gi(),m=gi(),v=gi(),i,l,mid,r,top=0; ll ans=0,dt=0,s,dn=0;//dt,dn是两个lazy标记 fp(i,1,n) d[i]=gi();//对产品需求量 fp(i,1,n) p[i]=gi();//订货单价 l=1,r=0; for (i=1;i<=n;i++) { while (l<=r&&p[i]-dt<=p[q[r]]) r--; s=d[i]; while (l<=r) if (s<w[q[l]]-dn) { ans+=(p[q[l]]+dt)*s,dn+=s,s=0;//dt为积下的存储费用 break; } else { ans+=(p[q[l]]+dt)*(w[q[l]]-dn); s-=w[q[l]]-dn,dn+=w[q[l++]]-dn;//dn为当前已使用的容量 } ans+=1LL*s*p[i]; q[++r]=i,w[i]=v+dn,p[i]-=dt; dt+=m; } printf("%lld\n",ans); return 0; } ```