首先想一想只有一组询问该怎么做。
菜烂掉比较不好处理,考虑反着来,每天都有菜变多,那么就可以贪心地每天选择收益最高的$m$份菜卖掉。具体实现的话,记录每样菜在什么时候烂光,在相应的一天以$a_i+s_i$的权值插进大根堆里,每次取出堆顶时判断一下,如果当前菜是第一次卖则只卖一个,然后把它以$a_i$的权值插回去;否则尽可能卖光,如果今天卖光了的话先临时存起来,今天结束了再插回去,防止堆顶始终是卖完的菜,引发死循环。
假设现在我们已经求出了$100000$天的答案,如何求出$99999$天的呢?我们发现菜烂掉有一个良好的性质:今天能卖的菜昨天一定也能卖。这样的话,我们就可以考虑把$99999m$份菜在前$99999$天卖掉,那么从$100000$天到$99999$天的损失就只有剩下第$100000$要卖的菜。同样地,我们用小根堆来维护最便宜的菜,把它们放在最后一天损失掉一定是最优的,这样就可以由$100000$天的答案倒退回$1$天的答案。
#include<cstdio> #include<algorithm> #include<vector> #include<queue> using namespace std; typedef long long ll; const int N=100050; char rB[1<<21],*rS,*rT,wB[1<<21]; int wp=-1; inline char gc(){return rS==rT&&(rT=(rS=rB)+fread(rB,1,1<<21,stdin),rS==rT)?EOF:*rS++;} inline void flush(){fwrite(wB,1,wp+1,stdout);wp=-1;} inline void pc(char c){if(wp+1==(1<<21))flush();wB[++wp]=c;} inline int rd(){ char c=gc(); while(c<48||c>57)c=gc(); int x=c&15; for(c=gc();c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c&15); return x; } short buf[25]; inline void wt(ll x){ short l=-1; while(x>9){ buf[++l]=x%10; x/=10; } pc(x|48); while(l>=0)pc(buf[l--]|48); pc('\n'); } int a[N],s[N],c[N],x[N],cnt[N],tmp[N],tmpl=-1; ll ans[N]; vector<int> p[N]; struct node{ int p,v; node(){} node(int p,int v):p(p),v(v){} inline bool operator <(const node &b)const{return v<b.v;} }; priority_queue<node> Q; struct nod{ int p,v; nod(){} nod(int p,int v):p(p),v(v){} inline bool operator <(const nod &b)const{return v>b.v;} }; priority_queue<nod> q; inline int Min(int a,int b){return a<b?a:b;} inline bool cmp(int x,int y){return p[x]<p[y];} int main(){ int n=rd(),m=rd(),k=rd(),i,j,lim,cur,t,tot=0; for(i=1;i<=n;++i){a[i]=rd();s[i]=rd();c[i]=rd();x[i]=rd();} for(i=1;i<=n;++i)if(x[i])p[Min(100000,(c[i]+x[i]-1)/x[i])].push_back(i); else p[100000].push_back(i); for(i=100000;i;--i){ for(j=0;j<p[i].size();++j)Q.push(node(p[i][j],a[p[i][j]]+s[p[i][j]])); if(Q.empty())continue; lim=m; while(lim&&!Q.empty()){ cur=Q.top().p;Q.pop(); if(!cnt[cur]){ cnt[cur]=1;ans[100000]+=a[cur]+s[cur];++tot;--lim; if(c[cur]>1)Q.push(node(cur,a[cur])); }else{ t=Min(lim,c[cur]-(i-1)*x[cur]-cnt[cur]); cnt[cur]+=t;ans[100000]+=(ll)a[cur]*t;tot+=t;lim-=t; if(c[cur]>cnt[cur])tmp[++tmpl]=cur; } } while(tmpl>=0){Q.push(node(tmp[tmpl],a[tmp[tmpl]]));--tmpl;} } for(i=1;i<=n;++i)if(cnt[i])if(cnt[i]==1)q.push(nod(i,a[i]+s[i])); else q.push(nod(i,a[i])); for(i=99999;i;--i){ ans[i]=ans[i+1]; if(tot<=m*i)continue; lim=tot-m*i; while(lim){ cur=q.top().p;q.pop(); if(cnt[cur]==1){cnt[cur]=0;ans[i]-=a[cur]+s[cur];--lim;} else{ t=Min(lim,cnt[cur]-1); ans[i]-=(ll)a[cur]*t;lim-=t; if((cnt[cur]-=t)==1)q.push(nod(cur,a[cur]+s[cur])); else q.push(nod(cur,a[cur])); } } tot=m*i; } while(k--)wt(ans[rd()]); flush(); return 0; }View Code