题解 P3826 【[NOI2017]蔬菜】

· · 题解

……网上的贪心题解太神啦……

并查集的做法实在是太精妙了……，这里说一个不是那么难想,也不那么难理解的做法，不需要并查集

本题题解

首先直接做的话根本无从下手，所以我们考虑一波奇怪的操作……比如时光倒流

现在我们反转这p天的流程，可以认为是某些菜会在某些时间突然出现，之后每一天都会运过来x_{i}单位的这种菜，这样就不需要考虑蔬菜会坏掉的问题了

我们发现无论我们怎么卖菜，都不会影响我们运菜的情况，不会存在我把贵的菜留着以后卖的情况，因为现在什么时候卖是一样的，但是后边可能会有更好的菜运过来，不如为将来腾出空间，所以现在各步的决策完全无关……，因此可以直接贪心，在每一天选择最贵的前m种菜卖掉，然后处理一下第一次卖菜的时候的额外收益即可

然后现在这个问题就变成了NOIP级别的大模拟题了，基本思路就是开一个堆然后乱七八糟维护一堆东西就够了

但是注意到k最大是10^5的量级,(因为每次询问互不相同)，我们考虑到这样做可能会华丽的T飞掉，因此我们需要考虑这个多组询问是否可以递推，即是否可以由p的答案递推到p-1的答案，答案是肯定的，我们当然可以递推了

由于我们前p天中的任意一个决策都可以在前p-1天做出的，而且我们发现卖菜的收益和时间无关，即我除了第一次卖菜之外，什么时候卖都是一样的，因此我们事实上会发现p和p-1的唯一区别就在于我们少卖了m个单位的菜

因此我们只需要挑出m个收益最小的菜然后扔掉不要就行了，这样就可以从p递推到p-1了……

为了体现题目的在线性，我直接打了一个p从1到1e5的表，然后每次处理询问的时候直接查表即可

上面说的只是一个大致的思路，真正写起来的话这道题会有一堆细节需要注意的地方

真正写起来你会发现这个东西其实并没有想像的那么好写，所以我们大致描述一下算法流程

1.生成p=1e5的解

1.1 每一天开一个vector暴力存储这一天会有什么蔬菜出现，我们认为x_{i}=0的菜全部在n=1e5的天出现，注意这里要用上取整计算天数

1.2从第1e5天从后向前扫，开一个堆存储蔬菜，每经过一天把这个vector里的所有菜按照a_{i}+s_{i}push到堆里

1.2.1，令lim=m，重复以下过程直到lim=0

1.2.2 从堆中拿出权值最大的菜，判断这种菜有没有被卖出过(这个可以开一个bool数组),如果卖出过的话计算这一天这种菜还有多少=c_{i}-(day-1)x_{i}-这种菜已经卖出的数量，然后和lim取个min去减，同时更新一下卖出的数量，然后把这个菜插入到一个队列里装着备用

1.2.2如果没有卖过，那么我们只卖一个，获得这a_{i}+s_{i}的权值，然后给堆里重新插入一个a_{i}的权值

1.2.3把刚才备用队列里的元素重新插回队列里，如果这种菜被卖光了就不必插入了

这样我们就生成了一个p=1e5的解，递推p-1的流程和刚才的类似，只是注意我们在扔菜的时候先扔到1，然后重新插一个权值为a_{i}+s_{i}的点到小根堆里去来处理放弃S_{i}的情况，然后我们就有了一张答案表，就可以O(1)的处理每个询问了~

算法复杂度O(pmlog(n))随机数据下m极有可能跑不满……具体细节的话看代码吧……

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=1e5+10;typedef long long ll;
int n;int m;int k;ll a[N];ll s[N];ll x[N];ll c[N];ll ans[N];
struct data
{
    ll v;int pos;
    friend bool operator <(data a,data b){return a.v<b.v;}
};priority_queue <data> pq;
struct nod
{
    ll v;int pos;
    friend bool operator <(nod a,nod b){return a.v>b.v;}
};priority_queue <nod> hp;
queue <int> us;int p=1e5;ll tot;
vector <int> app[N];bool used[N];ll sd[N];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){scanf("%d%d%d%d",&a[i],&s[i],&c[i],&x[i]);}
    for(int i=1;i<=n;i++)//处理每天出现的菜 
    {
        if(x[i]==0){app[p].push_back(i);}
        else {app[min((ll)p,(c[i]+x[i]-1)/x[i])].push_back(i);}
    }
    for(int i=p;i>=1;i--)
    {
        for(int j=0;j<app[i].size();j++)pq.push((data){a[app[i][j]]+s[app[i][j]],app[i][j]});
        if(pq.empty()){continue;}//先插入所有可能的菜 
        for(ll lim=m;lim&&!pq.empty();pq.pop())
        {
            data now=pq.top();//取出堆头 
            if(used[now.pos]==false)//获得si 
            {
                used[now.pos]=true;ans[p]+=now.v;sd[now.pos]++;lim--;
                if(c[now.pos]!=1){pq.push((data){a[now.pos],now.pos});}//重新插回去 
            }
            else //贪心的多取 
            {
                ll rem=c[now.pos]-sd[now.pos]-(i-1)*x[now.pos];//剩余的 
                ll del=min(rem,lim);ans[p]+=del*now.v;sd[now.pos]+=del;lim-=del;
                if(sd[now.pos]!=c[now.pos]){us.push(now.pos);}//放到回收的队列里 
            }
        }
        for(;!us.empty();us.pop()){int nw=us.front();pq.push((data){a[nw],nw});}//重新插回去 
    }
    for(int i=1;i<=n;i++)//递推ans 
    {
        if(sd[i]==1){hp.push((nod){s[i]+a[i],i});}//特判si 
        else if(sd[i]!=0){hp.push((nod){a[i],i});}tot+=sd[i];//统计下现在卖了多少菜 
    }
    for(int i=p-1;i>=1;i--)
    {
        ans[i]=ans[i+1];if(tot<=m*i){continue;}//如果还是可以卖一样的菜就不扔菜 
        for(ll lim=tot-m*i;lim&&!hp.empty();)//否则扔代价和最小的菜 
        {
            nod now=hp.top();hp.pop();//取出堆头 
            if(sd[now.pos]!=1)//扔掉非si部分 
            {
                ll del=min(sd[now.pos]-1,lim);
                sd[now.pos]-=del;lim-=del;ans[i]-=del*now.v;
                if(sd[now.pos]==1){hp.push((nod){a[now.pos]+s[now.pos],now.pos});}
                else {hp.push((nod){a[now.pos],now.pos});}//判一下是不是需要插回去 
            }
            else {lim--;sd[now.pos]--;ans[i]-=now.v;}//扔掉si部分 
        }tot=m*i;//更改tot 
    }
    for(int i=1,t;i<=k;i++){scanf("%d",&t);printf("%lld\n",ans[t]);}//查表出答案 
    return 0;//拜拜程序~ 
}