题解 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极有可能跑不满……具体细节的话看代码吧…… ```C #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;//拜拜程序~ } ```