目录
显示
题目链接
https://www.luogu.com.cn/problem/P3826
题解
神仙贪心题…
如果没有每天消失蔬菜这种烦人的操作的话,我们可以直接贪心解决:每次卖出价值最高的蔬菜即可,这个可以用优先队列实现。
现在加了个消失蔬菜的操作。直接处理消失蔬菜很烦人,我们可以让时光倒流——刚开始没有蔬菜,每天突然出现一些蔬菜。
每天出现的蔬菜的数量和价值都很容易处理,我们只需按之前说的那样贪心算出每天要卖出的蔬菜就行了。
然而还没完:本题有多组询问,每次都这样从头倒推肯定无法通过此题。我们需要想一种根据第 \(p\) 天的方案直接推 \(p-1\) 天方案的做法。
注意到第 \(p-1\) 天与第 \(p\) 天相比,我们只是少卖了些蔬菜。我们只需要从第 \(p\) 天的答案中扔掉价值最少的蔬菜不就能推出第 \(p-1\) 天的答案了吗?
这样我们就只用一次倒推就求出了所有的答案。
本题还有很多实现细节:
- 每个种类第一个卖出的蔬菜有奖励,因此需要将第一个蔬菜单独拿出来计算收入。
- 蔬菜可能卖不完,因此需要把这些卖不完的蔬菜重新放入堆中。
#include <cmath> #include <cassert> #include <iostream> #include <queue> #include <vector> #define MAXN 100005 using namespace std; const int p=100000; struct vegetable { long long a,s,c,x; }a[MAXN]; struct node { long long val; int u; bool operator<(const node&a)const { return val<a.val; } bool operator>(const node&a)const { return val>a.val; } }; bool vis[MAXN]; long long ans[MAXN],s[MAXN]; priority_queue<node> q1; priority_queue<node,vector<node>,greater<node> > q2; queue<int> q; vector<int> v[MAXN]; int main() { int n,m,k; cin>>n>>m>>k; for(int i=1;i<=n;i++) cin>>a[i].a>>a[i].s>>a[i].c>>a[i].x; for(int i=1;i<=n;i++) if(!a[i].x)v[p].push_back(i); else v[min(p,int(ceil(1.0*a[i].c/a[i].x)))].push_back(i); for(int i=p;i;i--) { for(int j=0;j<v[i].size();j++) q1.push({a[v[i][j]].a+a[v[i][j]].s,v[i][j]}); if(q1.empty())continue; long long rem=m; while(rem) { if(q1.empty())break; int u=q1.top().u; long long val=q1.top().val; q1.pop(); if(!vis[u]) { vis[u]=1,ans[p]+=val,s[u]++,rem--; if(a[u].c!=1)q1.push({a[u].a,u}); } else { long long num=a[u].c-s[u]-(i-1)*a[u].x; long long used=min(num,rem); ans[p]+=used*val;s[u]+=used;rem-=used; if(s[u]!=a[u].c)q.push(u); } } while(!q.empty()) { int u=q.front(); q.pop(); q1.push({a[u].a,u}); } } long long tot=0; for(int i=1;i<=n;i++) { if(s[i]==1)q2.push({a[i].a+a[i].s,i}); else if(s[i])q2.push({a[i].a,i}); tot+=s[i]; } for(int i=p-1;i;i--) { ans[i]=ans[i+1]; if(tot<=m*i)continue; long long rem=tot-m*i; while(rem) { if(q2.empty())break; int u=q2.top().u; long long val=q2.top().val; q2.pop(); if(s[u]!=1) { long long used=min(rem,s[u]-1); s[u]-=used,rem-=used,ans[i]-=used*val; if(s[u]==1)q2.push({a[u].a+a[u].s,u}); else q2.push({a[u].a,u}); } else rem--,s[u]--,ans[i]-=val; } tot=m*i; } while(k--) { int t; cin>>t; cout<<ans[t]<<endl; } return 0; }