[NOI2017]蔬菜

你的名字 2021-12-20 10:19 196阅读 0赞

# \[NOI2017\]蔬菜 #

[题目描述][Link 1]

大意就是有\\(n\\)种物品，第\\(i\\)个物品有\\(c\_i\\)个，单价是\\(a\_i\\)。然后每天你可以卖出最多\\(m\\)个物品。每天结束后第\\(i\\)种物品会减少\\(x\_i\\)个。第一次出售\\(i\\)物品时还会额外获得\\(s\_i\\)的收益。

每次询问给出\\(p\\)，问\\(p\\)天能得到的最大收益。

\\(1\\leq n,p\\leq 10^5,1\\leq m\\leq 10,1\\leq a\_i,c\_i\\leq 10^9\\)。

神仙题啊！不会网络流，不会贪心，直接自闭。

[Orz][]

### 60分的网络流做法 ###

因为很容易发现这个题状态太大，无法\\(DP\\)，所以我们考虑费用流之类的东西。然后我们发现这个题每个物品的上限时刻在变化，很难建图。

对于这种流量变化的费用流我们考虑拆点。我们将每种蔬菜拆成\\(P\\)个点，第\\(i\\)个点到汇点的流量就是第\\(i\\)天比第\\(i+1\\)天多的数量。我们还应该额外拆一个点表示第一次出售。然后第\\(i\\)个点向第\\(i+1\\)个点连边。

我们增广\\(P\\)次，就得到了\\(1\\)到\\(P\\)的答案。

### 100分的贪心算法 ###

我们发现每天有蔬菜减少非常不好做，于是我们考虑倒着做。这样相当于每天我们会得到一些蔬菜。所以我们就可以每次选收益最大的蔬菜来卖。

具体实现有点复杂。先开一个堆。记录每种蔬菜最晚在什么时候出现。当倒推到第\\(i\\)天时，将在最晚在当天出现的蔬菜丢进堆里。每次取堆顶的蔬菜来卖。

这样我们就得到了\\(P\\)天的答案。

然后考虑递推出\\(1\\)到\\(P-1\\)的答案。相当于说我们要把卖出的蔬菜删除掉。一个比较显然的结论就是我们尽量在天数偏小的时候删除（因为我们卖蔬菜肯定也是越早卖越好）。删除的时候就一直删除当前价值最小的。

不用考虑会不会删除操作时出现了不合法的情况。因为我们发现删除的时间是没有影响的。可以这么感性理解分析：假设我们递推到第\\(i\\)天，要删除一些第\\(k\\)种蔬菜，那么我们就将相应的卖出操作撤销，在它之后的卖出操作全部提前，这肯定也是合法的。

据说这就是模拟费用流。

代码：

#include<bits/stdc++.h>
    #define ll long long
    #define N 100005
    
    using namespace std;
    inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
    
    int n,m,k;
    ll ans;
    int a[N],s[N],c[N],x[N];
    struct node {
        ll id,val;
        node() {val=id=0;}
        node(int i,int v) {val=v,id=i;}
        bool operator <(const node &a)const {return val<a.val;}
    };
    priority_queue<node>q;
    const int P=100000;
    int sold;
    vector<int>ap[N];
    vector<int>tem;
    int used[N];
    ll Ans[N];
    int main() {
        n=Get(),m=Get(),k=Get();
        for(int i=1;i<=n;i++) {
            a[i]=Get(),s[i]=Get(),c[i]=Get(),x[i]=Get();
            if(!x[i]) ap[P].push_back(i);
            else ap[min(P,(c[i]+x[i]-1)/x[i])].push_back(i);
        }
        
        for(int i=P;i>=1;i--) {
            for(int j=0;j<ap[i].size();j++) {
                q.push(node(ap[i][j],s[ap[i][j]]+a[ap[i][j]]));
            }
            tem.clear();
            int res=m;
            while(res) {
                if(!q.size()) break;
                int id=q.top().id,val=q.top().val;
                q.pop();
                if(!used[id]) {
                    res--;
                    used[id]=1;
                    ans+=val;
                    q.push(node(id,a[id]));
                } else {
                    int now=min(res,c[id]-used[id]-(i-1)*x[id]);
                    res-=now;
                    used[id]+=now;
                    ans+=1ll*now*val;
                    if(used[id]<c[id]) tem.push_back(id);
                }
            }
            sold+=m-res;
            for(int j=0;j<tem.size();j++) q.push(node(tem[j],a[tem[j]]));
        }
        
        while(q.size()) q.pop();
        for(int i=1;i<=n;i++) {
            if(used[i]==1) q.push(node(i,-s[i]-a[i]));
            else if(used[i]>1) q.push(node(i,-a[i]));
        }
        
        Ans[P]=ans;
        for(int i=P;i>1;i--) {
            tem.clear();
            int res=max(0,sold-(i-1)*m);
            while(res) {
                if(!q.size()) break;
                int id=q.top().id,val=q.top().val;
                q.pop();
                if(used[id]==1) {
                    sold--;
                    used[id]--;
                    res--;
                    ans+=val;
                } else {
                    int now=min(res,used[id]-1);
                    used[id]-=now;
                    res-=now;
                    ans+=1ll*now*val;
                    sold-=now;
                    if(used[id]==1) q.push(node(id,-s[id]-a[id]));
                    else q.push(node(id,-a[id]));
                }
            }
            Ans[i-1]=ans;
        }
        while(k--) {
            int x=Get();
            cout<<Ans[x]<<"\n";
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hchhch233/p/10566307.html

[Link 1]: https://www.luogu.org/problemnew/show/P3826
[Orz]: https://www.cnblogs.com/cjyyb/p/9743710.html