1 条题解
-
1
#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;//拜拜程序~ }
- 1
信息
- ID
- 2759
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者