[NOI2017]蔬菜（贪心+递推）

这题很有思维难度，乍一看基本无从下手。

给每个蔬菜钦定退役的时间显然很困难，可以考虑让时光倒流，从后向前递推，然后就变成了某个时间点有一部分蔬菜服役，而已经服役的蔬菜不会退役了。然后就可以直接考虑贪心，每种第一个出现的蔬菜，显然可以单独考虑，加上s[i]，然后把蔬菜放到堆里面，就可以在O(pmlogn)的复杂度下求出f[p]了，用堆维护即可，假定p=1e5。

然后发现这个玩意可以递推求解，第p-1天在役的蔬菜一定不少于第p天的，显然只需去掉利润最少的m个即可。

#include<bits/stdc++.h>

#define pb push_back

using namespace std;

const int N=1e5+;

typedef long long ll;

typedef pair<int,int>pii;

struct node{int v,x;}st[N];

bool operator<(node a,node b){return a.v<b.v;}

int n,m,T,P=1e5,top,sum,a[N],s[N],c[N],x[N],used[N];

ll ans[N];

bool vis[N];

vector<int>d[N];

priority_queue<node>q;

int main()

{

    scanf("%d%d%d",&n,&m,&T);

    for(int i=;i<=n;i++)scanf("%d%d%d%d",&a[i],&s[i],&c[i],&x[i]);

    for(int i=;i<=n;++i)if(!x[i])d[P].pb(i);else d[min(P,(c[i]+x[i]-)/x[i])].pb(i);

    for(int i=P;i;i--)

    {

        for(int j=;j<d[i].size();j++)q.push((node){a[d[i][j]]+s[d[i][j]],d[i][j]});

        if(q.empty())continue;

        int j=m;

        while(j&&!q.empty())

        {

            node u=q.top();q.pop();

            if(!vis[u.x])

            {

                vis[u.x]=,ans[P]+=u.v,used[u.x]++,--j;

                if(c[u.x]>)q.push((node){a[u.x],u.x});

            }

            else{

                int rest=min(j,c[u.x]-used[u.x]-(i-)*x[u.x]);

                ans[P]+=1ll*rest*u.v,used[u.x]+=rest,j-=rest;

                if(used[u.x]!=c[u.x])st[++top]=(node){a[u.x],u.x};

            }

        }

        while(top)q.push(st[top--]);

    }

    while(!q.empty())q.pop();

    for(int i=;i<=n;i++)sum+=used[i];

    for(int i=;i<=n;i++)

    if(used[i]==)q.push((node){-s[i]-a[i],i});else if(used[i])q.push((node){-a[i],i});

    for(int i=P-;i;i--)

    {

        ans[i]=ans[i+];

        while(sum>i*m&&!q.empty())

        {

            node u=q.top();

            q.pop(),u.v*=-;

            if(used[u.x]>)

            {

                int rest=min(sum-i*m,used[u.x]-);

                used[u.x]-=rest,sum-=rest,ans[i]-=1ll*rest*u.v;

                if(used[u.x]==)q.push((node){-a[u.x]-s[u.x],u.x});

                else q.push((node){-a[u.x],u.x});

            }

            else sum--,used[u.x]--,ans[i]-=u.v;

        }

    }

    for(int i=,x;i<=T;i++)scanf("%d",&x),printf("%lld\n",ans[x]);

}