BZOJ4946 NOI2017蔬菜（贪心+堆）

　　容易想到一个费用流做法：将每种蔬菜拆成p种，对应p个过期时间，每一种向可以卖的时间连边，第一次卖的奖励算在最晚过期的一种里。对于天数动态加点。不过这样边数太多了，因为第i天能卖的第i-1天一定能卖，可以改成每一种只向过期时间连边然后第i天向第i-1天连边。这样就有60分了。但费用流没有什么优化空间了。

　　如果蔬菜不会过期的话，贪心做法非常显然。那么，考虑让时光倒流。这样蔬菜只会每天增加，每次贪心的选出价值最大的行了。对于奖励，拆成两种蔬菜就好。

　　考虑对于单次询问具体应该怎么做。用一个大根堆维护应该选哪些蔬菜。堆里蔬菜分为两类，一类是每天都能拿的，一类只能拿一次的。每次从堆顶拿出m个蔬菜，如果是每天都能拿的再恢复回去，注意考虑各种情况。

　　然后考虑多次询问。我们需要从前p天的答案倒推出前p-1天的答案。注意到第p天能选择的第p-1天一定能选择。并且前p-1天的最优选择应该包含在前p天的最优选择内，否则第p天的选择本来就更少没有理由丢掉之前的较优选择。那么从答案里去掉最小的几个使得剩下的不超过(p-1)m个就可以了。

　　感觉写的姿势并不对，于是变的异常难写和丑陋不堪。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

#include<stack>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 100010

#define inf 1000000000

#define ll long long

int n,m,k,cnt=;

ll tot=,ans[N];

struct data{int v,c,x;

}a[N<<];

struct data2{int i,x;

}Q[N];

struct data3

{

    int tim,cnt,val;

    bool operator <(const data3&a) const

    {

        return val<a.val;

    }

}choose[N*];

vector<data3> app[N],rec[N];

priority_queue<data3> q;

stack<data3> undo;

bool cmp(const data2&a,const data2&b)

{

    return a.x>b.x;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4946.in","r",stdin);

    freopen("bzoj4946.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read(),k=read();

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

    a[i].v=read(),a[i+n].v=a[i].v+read(),a[i].c=read()-,a[i+n].c=,a[i].x=read(),a[i+n].x=;

    n<<=;

    for (int i=;i<=k;i++) Q[i].i=i,Q[i].x=read();

    sort(Q+,Q+k+,cmp);

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

    if (a[i].x==)

    {

        if (i<=(n>>)) app[Q[].x].push_back((data3){,a[i].c,a[i].v});

        else app[a[i-(n>>)].x?min(Q[].x,a[i-(n>>)].c/a[i-(n>>)].x+):Q[].x].push_back((data3){,a[i].c,a[i].v});

    }

    else

    {

        if (a[i].c-1ll*a[i].x*Q[].x>) app[Q[].x].push_back((data3){,a[i].c-1ll*a[i].x*Q[].x,a[i].v});

        else if (a[i].c%a[i].x) app[a[i].c/a[i].x+].push_back((data3){,a[i].c%a[i].x,a[i].v});

        rec[min(a[i].c/a[i].x,Q[].x)].push_back((data3){min(a[i].c/a[i].x,Q[].x)+,a[i].x,a[i].v});

    }

    for (int i=Q[].x;i;i--)

    {

        for (int j=;j<app[i].size();j++) q.push(app[i][j]);

        for (int j=;j<rec[i].size();j++) q.push(rec[i][j]);

        int t=m;

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

        {

            if (q.top().tim==)

            {

                if (t>=q.top().cnt) ans[Q[].i]+=1ll*q.top().cnt*q.top().val,t-=q.top().cnt,choose[++cnt]=q.top();

                else {ans[Q[].i]+=1ll*t*q.top().val;undo.push((data3){,q.top().cnt-t,q.top().val});choose[++cnt]=(data3){,t,q.top().val};t=;}

            }

            else

            {

                int tmp=q.top().cnt*(q.top().tim-i);

                if (t>=tmp)

                {

                    ans[Q[].i]+=1ll*tmp*q.top().val;

                    choose[++cnt]=(data3){,tmp,q.top().val};

                    undo.push((data3){i,q.top().cnt,q.top().val});

                    t-=tmp;

                }

                else

                {

                    ans[Q[].i]+=1ll*t*q.top().val;

                    if (t>=q.top().cnt) choose[++cnt]=(data3){,q.top().cnt*(t/q.top().cnt),q.top().val};

                    undo.push((data3){q.top().tim-(t-)/q.top().cnt-,q.top().cnt,q.top().val});

                    if (t%q.top().cnt) choose[++cnt]=(data3){,t%q.top().cnt,q.top().val},undo.push((data3){,q.top().cnt-t%q.top().cnt,q.top().val});

                    t=;

                }

            }

            q.pop();

        }

        while (!undo.empty()) q.push(undo.top()),undo.pop();

    }

    sort(choose+,choose+cnt+);

    int tot=;for (int i=;i<=cnt;i++) tot+=choose[i].cnt;

    int t=;long long sum=ans[Q[].i];cnt=;

    for (int i=Q[].x-;i;i--)

    {

        while (tot>i*m)

        {

            if (tot-i*m>=choose[cnt].cnt) sum-=1ll*choose[cnt].cnt*choose[cnt].val,tot-=choose[cnt++].cnt;

            else sum-=1ll*choose[cnt].val*(tot-i*m),choose[cnt].cnt-=tot-i*m,tot=i*m;

        }

        if (i==Q[t].x) ans[Q[t++].i]=sum;

    }

    for (int i=;i<=k;i++) printf(LL,ans[i]);

    return ;

}

巴特西

BZOJ4946 NOI2017蔬菜（贪心+堆）

最新文章

热门文章