注意每一单位蔬菜的变质时间是固定的，不随销售发生变化
固定的......
就是每一个单位的蔬菜在哪一天变质是早就定好了的
发现从第一天推到最后一天很不好搞
考虑反过来，从最后一天推到第一天，这样就相当于每天多一些蔬菜
不管现在怎么卖都不会影响下一天多的蔬菜，不会出现贵的留到后面卖的操作，因为后面蔬菜只会越来越多，不如把空间留给之后可能会出现的更好的菜
可以直接贪心了，每天都卖最贵的 $m$ 单位蔬菜，这样就一定是最优的
然后就是维护每天的各种菜了，开个堆并维护一堆东西，没什么思维...
但是这样还不够，有多组询问
继续倒过来考虑，每天菜只会越来越多，发现 卖 $p$ 天的任意一种操作 卖 $p-1$ 天都能做
唯一的区别只是卖 $p-1$ 天少卖了几个菜
所以可以先处理出 $p=10^5$ 时的答案并把各种操作存一下，然后扔掉价值最小的几种操作直到总操作数在 $p-1$ 天也能做出，就能从 $p$ 推到 $p-1$ 了
然后就可以预处理出所有的询问了
具体维护的时候其实并不容易......看代码注释吧
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7; int n,m,K,a[N],s[N],c[N],x[N],sum[N]; //n,m,k,a,s,c,x意义同题面,sum[i]维护当前编号为i的菜卖出的数量 bool fir[N];//判断是否是第一次卖 ll ans[N];//存答案 struct dat1{ int val,id;//蔬菜的价值，编号 inline bool operator < (const dat1 &tmp) const { return val<tmp.val; } }tmp[17];//队列,存今天卖完的菜编号 priority_queue <dat1> Q1;//维护当前各种存在的蔬菜 struct dat2{ int val,id;//卖的菜的价值，编号 inline bool operator < (const dat2 &tmp) const { return val>tmp.val; } }; priority_queue <dat2> Q2;//维护当前卖的各种菜 vector <int> V[N];//V[i][j]维护在第i天 第一次出现的 第j种菜的编号 void pre_work() { for(int i=1;i<=n;i++) { if(x[i]&& c[i]/x[i]+(c[i]%x[i]!=0)<=1e5 )//注意特判 V[ c[i]/x[i]+(c[i]%x[i]!=0) ].push_back(i); else Q1.push((dat1){a[i]+s[i],i});//先加入第一次卖的价值 } for(int now=100000;now>0;now--)//从最后一天考虑 { for(int i=V[now].size()-1;i>=0;i--) Q1.push((dat1){ a[V[now][i]]+s[V[now][i]] , V[now][i] }); //把每天的新菜加入堆,价值为第一次卖的价值 int cnt=0;//tmp队列头 for(int t=0;t<m&&!Q1.empty();)//t记录今天已经卖了多少菜 { dat1 y=Q1.top(); Q1.pop(); int z=y.id;//找出价值最大的菜 if(fir[z])//不是第一次卖 { int num=min(m-t/*最多能卖的量*/, c[z]-(now-1)*x[z]-sum[z]/*当前此菜的量*/ ); sum[z]+=num; t+=num; ans[100000]+=1ll*num*y.val;//注意long long if(sum[z]!=c[z]) tmp[++cnt]=y;//如果没完全卖完就加入队列(今天的量已经完了) } else//第一次卖 { sum[z]++; t++; ans[100000]+=y.val; fir[z]=1;//只卖一单位 if(sum[z]!=c[z]) Q1.push((dat1){a[z],z});//把非第一次卖的价值加入堆 } } for(int j=1;j<=cnt;j++) Q1.push(tmp[j]);//下一天了，把今天卖完的菜补充回来 } int tot=0;//记录卖的总数 for(int i=1;i<=n;i++)//记录各种操作 { if(sum[i]==1) Q2.push((dat2){a[i]+s[i],i});//特判第一次 else if(sum[i]) Q2.push((dat2){a[i],i}); tot+=sum[i]; } for(int i=1e5-1;i;i--)//逆推ans { ans[i]=ans[i+1]; if(tot<=m*i) continue;//卖的数量合法就不用少卖 for(int t=0;t<tot-m*i&&!Q2.empty();)//t记录当前少卖的数量 { dat2 y=Q2.top(); Q2.pop(); int z=y.id;//把价值最小的操作拿出 if(sum[z]!=1)//不是第一次 { int num=min(sum[z]-1/*刚好减少到第一次*/,tot-m*i-t/*刚好合法*/); sum[z]-=num; t+=num; ans[i]-=1ll*num*y.val; if(sum[z]==1) Q2.push((dat2){a[z]+s[z],z});//剩下一单位,把第一次的价值加入 else Q2.push((dat2){a[z],z});//还不止一单位 } else sum[z]--,t++,ans[i]-=y.val;//第一次卖 } tot=m*i;//更新tot } } int main() { n=read(),m=read(),K=read(); for(int i=1;i<=n;i++) a[i]=read(),s[i]=read(),c[i]=read(),x[i]=read(); pre_work(); while(K--) printf("%lld ",ans[read()]); return 0; }