[NOI2017]蔬菜

贪心 堆 并查集

题面

戳我

解析

一道质量不错的贪心题。
我一开始的思路就是删掉菜这个操作太麻烦了，从后往前加菜会方便很多。
于是从后往前推，每天加上在当天腐烂完毕的蔬菜，然后拿个堆贪心地取，就可以得到卖$10^5$天的答案。
当然要注意每天处理的是前面$x$天的购买情况（而不是只有第$x$天腐烂的）。
然后再从后往前推答案，由于贪心过程中第$x$天买的蔬菜实际上可以在$1～x-1$中任意一天买，所以每天删掉价值前$m$（可能不满）小的蔬菜即可，这个可以用堆维护。
复杂度$O(nQlogn)$

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define pb(a) push_back(a)
#define ll long long
#define re register
#define il inline
using namespace std;
const int N=1e5+100;
int n,m,k,a[N],s[N],c[N],x[N],use[N],sta[N],top,num;
ll ans[N];
struct dat
{
  int w,id;
  il bool operator < (const dat &o) const {return w<o.w;}
  il bool operator > (const dat &o) const {return w>o.w;}
};
priority_queue<dat>Q;
priority_queue<dat,vector<dat>,greater<dat> >Q1;
vector<int>v[N];
il int min(re int x,re int y){return x<y?x:y;}
il int max(re int x,re int y){return x>y?x:y;}
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();m=gi();k=gi();
  for(int i=1;i<=n;++i)
    {
      a[i]=gi(),s[i]=gi(),use[i]=c[i]=gi(),x[i]=gi();
      if(!x[i]) v[(int)1e5].pb(i);
      else v[min((int)1e5,(c[i]+x[i]-1)/x[i])].pb(i);
    }
  re ll res=0,now=1e5,tot;
  while(now)
  {
    for(re int i=0;i<v[now].size();++i) Q.push((dat){a[v[now][i]]+s[v[now][i]],v[now][i]});
    tot=m;
    while(tot)
    {
      if(Q.empty()) break;
      re dat t=Q.top();Q.pop();
      if(use[t.id]==c[t.id])
    {
      --use[t.id];--tot;
      res+=t.w;
      if(use[t.id]) Q.push((dat){a[t.id],t.id});
    }
      else
    {
      re ll can_=min(tot,use[t.id]-x[t.id]*(now-1));can_=max(can_,0ll);
      res+=can_*t.w;
      tot-=can_;use[t.id]-=can_;
      if(use[t.id]) sta[++top]=t.id;
    }
    }
    for(int i=1;i<=top;++i) Q.push((dat){a[sta[i]],sta[i]});top=0;
    --now;
  }
  for(int i=1;i<=n;++i)
    {
      if(use[i]==c[i]-1) Q1.push((dat){a[i]+s[i],i});
      else if(use[i]!=c[i]) Q1.push((dat){a[i],i});
      num+=c[i]-use[i];
    }
  ans[(int)1e5]=res;
  for(int o=1e5-1;o;--o)
    {
      while(num>o*m)
      {
    re dat t=Q1.top();Q1.pop();
        re ll los=min(c[t.id]-use[t.id]-1,num-o*m);
    if(use[t.id]==c[t.id]-1)
    {
          res-=t.w;--num;++use[t.id];
    }
    else if(use[t.id]<c[t.id]-1)
    {
          res-=t.w*los;num-=los;use[t.id]+=los;
      if(use[t.id]<c[t.id]-1) Q1.push((dat){a[t.id],t.id});
      else Q1.push((dat){a[t.id]+s[t.id],t.id});
        }
      }
      ans[o]=res;
    }
  for(int i=1;i<=k;++i) printf("%lld\n",ans[gi()]);
  return 0;
}

然而其实没必要那么麻烦。
题目数据范围其实不够大，例如蔬菜最多卖$10^6$份，这意味着我们可以用更轻松愉快的方法水过这道题。
我们其实可以直接统计卖的第$i$份是哪种菜。
这个也可以按照价格贪心，用堆维护。
每次从它腐烂的最后一天开始卖（可以证明这样不会更劣），如果那天有$m$份了就把它的并查集父亲赋为前一天。（这个和“疯狂的馒头”套路是一样的）
这样复杂度差不多，但常数更小代码更短，简直人赢。

#include<iostream>
#include<cstdio>
#include<queue>
#define ll long long
#define re register
#define il inline
#define P pair<int,int>
using namespace std;
const int N=1e5+100;
int n,m,k,a[N],s[N],c[N],x[N],mx=1e5,res[N],f[N],p;
ll ans[N*10];
priority_queue<P>Q;
il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
int main()
{
  ios::sync_with_stdio(false);
    cin>>n>>m>>k;
  for(re int i=1;i<=n;++i) cin>>a[i]>>s[i]>>c[i]>>x[i],Q.push(P(a[i]+s[i],i));
  for(re int i=1;i<=mx;++i) f[i]=i,res[i]=m;
    re int now=0;
    while(!Q.empty())
    {
        re int i=Q.top().second,w=Q.top().first,fa=find(x[i]?min(mx,(c[i]+x[i]-1)/x[i]):mx);
        if(!fa) {Q.pop();continue;}
        --res[fa];if(!res[fa]) f[fa]=find(fa-1);
        --c[i];if(!c[i]) Q.pop();else if(w>a[i]) Q.pop(),Q.push(P(a[i],i));
        ++now;ans[now]=ans[now-1]+w;
    }
    while(k--) cin>>p,printf("%lld\n",ans[min(p*m,now)]); 
  return 0;
}