【题解】[NOI2017] 蔬菜 堆模拟费用流/贪心 loj2306 — Qiuly

首先需要解释一下题意问题。

假设一天有 $a$ 个单位的蔬菜变质，而你这一天卖掉了 $b\leq a$ 个蔬菜，那么只有 $a-b$ 个单位的蔬菜会被丢掉。

考虑将每天建一个点表示，对于一种蔬菜，将其第 $i$ 天变质的个数记到第 $i$ 天的点上，也就是从 $S$ 连边。这个时间点的蔬菜不能放到更晚去卖，但是可以在更早卖掉，所以每一天向上一天连边。

建好图后跑费用流即可，大概有 $60$ 分。

数据范围比较迷惑，考虑模拟费用流。时间倒流，用堆维护当前的蔬菜即可，预计得分 $80$ 分。

具体细节就是，因为晚变质的可以放到之前卖，所以每一次都要从最终时间点开始扫。至于一个时间点能不能买蔬菜，还得看这个时间点在不在询问范围之内。

（之前写模拟费用流还傻乎乎的连边，然后用树状数组维护才强行过 $80$ …

考虑满分做法，复杂度瓶颈在于每一次询问都要搞一遍。

考虑从第 $i$ 天的答案推到 $i-1$ 天的答案，因为第 $i$ 天能卖的蔬菜 $i-1$ 天也能卖，用堆维护第 $i$ 天买了哪些蔬菜，然后因为 $i-1$ 天最多卖 $(i-1)m$ 个蔬菜，将超出上限的蔬菜弹掉，优先弹贡献最小的蔬菜即可。

难点主要在：理解题意，网络流模型和最后到贪心的转变。

代码难度不高。

const int N=1e5+5;
int n,m,k,L,lim;

ll ans[N];
int a[N],s[N],c[N],x[N],q[N],tot[N];
std::vector <int> hep[N];

std::vector <std::pair <int,int> > trash;
std::priority_queue <std::pair <int,int> > q1,q2;

inline void init() {
    ll res=0;
    for(int d=L;d;--d) {
        for(int i:hep[d]) q1.push(mkp(a[i]+s[i],i));

        for(int qwq=m;qwq&&!q1.empty();) {
            int i=q1.top().se; q1.pop();
            if(!tot[i]) {
                res+=a[i]+s[i],++tot[i],--qwq;
                if(tot[i]!=c[i]) q1.push(mkp(a[i],i));
            } else {
                int now=min(qwq,c[i]-tot[i]-(d-1)*x[i]);
                res+=1ll*a[i]*now,tot[i]+=now,qwq-=now;
                if(tot[i]!=c[i]) trash.pb(mkp(a[i],i));
            }
        }
        while(trash.size()) q1.push(trash.back()),trash.pp();
    }
    ans[L]=res;
}

inline void solve() {
    int all=0;
    for(int i=1;i<=n;++i) if(tot[i])
        q2.push(mkp(-((tot[i]==1)?a[i]+s[i]:a[i]),i)),all+=tot[i];

    for(int d=L-1;d;--d) {
        ans[d]=ans[d+1];
        if(all<=m*d) continue;

        for(int qwq=all-m*d;qwq&&!q2.empty();) {
            int i=q2.top().se; q2.pop();
            if(tot[i]==1) ans[d]-=a[i]+s[i],--tot[i],--qwq;
            else {
                int now=min(qwq,tot[i]-1);
                ans[d]-=1ll*a[i]*now,tot[i]-=now,qwq-=now;
                q2.push(mkp(-((tot[i]==1)?a[i]+s[i]:a[i]),i));
            }
        }
        all=m*d;
    }
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("code.in","r",stdin);
        freopen("code.out","w",stdout);
    #endif
    IN(n,m,k);
    for(int i=1;i<=n;++i) IN(a[i],s[i],c[i],x[i]);
    for(int i=1;i<=k;++i) IN(q[i]),chkmax(L,q[i]);
    for(int i=1;i<=n;++i) hep[x[i]?min(L,(c[i]+x[i]-1)/x[i]):L].pb(i);

    init(),solve();
    for(int i=1;i<=k;++i) printf("%lld\n",ans[q[i]]);
    return 0;
}