[洛谷 3826][NOI2017]蔬菜

题目链接

https://www.luogu.com.cn/problem/P3826

题解

神仙贪心题…

如果没有每天消失蔬菜这种烦人的操作的话，我们可以直接贪心解决：每次卖出价值最高的蔬菜即可，这个可以用优先队列实现。

现在加了个消失蔬菜的操作。直接处理消失蔬菜很烦人，我们可以让时光倒流——刚开始没有蔬菜，每天突然出现一些蔬菜。

每天出现的蔬菜的数量和价值都很容易处理，我们只需按之前说的那样贪心算出每天要卖出的蔬菜就行了。

然而还没完：本题有多组询问，每次都这样从头倒推肯定无法通过此题。我们需要想一种根据第 \(p\) 天的方案直接推 \(p-1\) 天方案的做法。

注意到第 \(p-1\) 天与第 \(p\) 天相比，我们只是少卖了些蔬菜。我们只需要从第 \(p\) 天的答案中扔掉价值最少的蔬菜不就能推出第 \(p-1\) 天的答案了吗？

这样我们就只用一次倒推就求出了所有的答案。

本题还有很多实现细节：

1. 每个种类第一个卖出的蔬菜有奖励，因此需要将第一个蔬菜单独拿出来计算收入。
2. 蔬菜可能卖不完，因此需要把这些卖不完的蔬菜重新放入堆中。

#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;
}