P3826 [NOI2017] 蔬菜 题解

思路

首先注意这题的蔬菜并不是每天固定变质 $x_i$ 颗，而是一开始每颗蔬菜变质的时间已经定好了，比如一种蔬菜的 $x_i=3$，则我在第 $1$ 天卖出 $2$ 颗在第 $1$ 天变质的蔬菜后第一天结束只会变质 $1$ 颗。

那么这道题就转化为了一个有截止时间的贪心问题，考虑倒序枚举每种蔬菜的变质日期，先售出变质日期较晚地蔬菜，进行贪心可得每颗蔬菜要尽量晚地售出。

具体地，用并查集来表示当前变质日期在第 $i$ 天的蔬菜最晚可以在哪天售出，然后每次取当前价值最高的蔬菜售出。

具体细节较多，详见代码。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
int a[100010],s[100010],c[100010],x[100010]; 
ll ans[1000010];//ans[i]表示售出i颗蔬菜的最大价值 
int fa[100010],w[100010];//并查集,w[i]表示当前天数已经售卖了即可蔬菜 
int find(int x){
	return fa[x]=(fa[x]==x?x:find(fa[x]));
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>k;
	priority_queue<pair<int,int>> q;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>s[i]>>c[i]>>x[i];
		q.push({a[i]+s[i],i});//记得第一次是a[i]+s[i] 
	}
	for(int i=1;i<=100000;i++){//初始化 
		fa[i]=i;w[i]=0;
	}
	int now=0;
	while(!q.empty()){
		int v=q.top().first,i=q.top().second;
		q.pop();
		int p;
		if(x[i]==0)p=100000;//没有变质日期 
		else p=find(min(100000,(c[i]-1)/x[i]+1)/*第c[i]颗蔬菜的变质日期（从大到小枚举）*/);
		if(p<=0)continue;//特判无法售出 
		c[i]--;//蔬菜剩余数量减一 
		if(c[i])q.push({a[i],i});//有剩余蔬菜就继续卖 
		w[p]++;//第p天售出蔬菜数量加一 
		if(w[p]==m)fa[find(p)]=fa[find(p-1)];//如果第p天不能继续售卖就到p-1天去卖 
		now++;//售出蔬菜数量加一 
		ans[now]=ans[now-1]+v;//记录答案 
	}
	while(k--){
		int p;
		cin>>p;
		cout<<ans[min(now,p*m)]<<'\n';//注意是p*m 
	}
	return 0;
}

注意到 $n\times m$ 不大，所以其实可以把 $1$ 天拆成 $m$ 天，每天只能卖 $1$ 个单位的蔬菜，从而解除每天销售量的限制。而变质就相当于是对每 $x_i$ 个单位的蔬菜卖出的时间限制。

然后对于每种蔬菜，都可以拆出一种价值为 $a_i+s_i$，库存为 $1$ 个单位的新蔬菜，由于新蔬菜的价值比原蔬菜大，其它限制相同，所以不可能卖了原蔬菜而不卖新蔬菜，从而可以消除额外收益的影响。

考虑先计算最后一天的收益，根据贪心，我们将所有蔬菜按价值从大到小排序，并将蔬菜尽量晚的卖出去，也就是我们需要找到蔬菜限制内最晚的空闲时间将其卖出，这部分可以用并查集维护，只需令被占用的位置指向空位。

对于其它时间的答案，只需将天数从大到小扫描，每次找出已卖掉的价值最小的蔬菜并将其取消卖出，由于空位会被当前最晚卖出的蔬菜填补，所以不影响正确性。

代码如下，具体看注释：

#include<bits/stdc++.h>
using namespace std;
struct vegetable{
	int v,c,x,l;
	//分别表示 价值、库存、变质周期、期限（对于无变质周期的蔬菜而言） 
};
bool cp(vegetable x,vegetable y){
	return x.v>y.v;
}
const int lim=1e5;
int n,m,q,fa[1000010];
long long ans[100010];
vector<vegetable> vg;
priority_queue<int> h;
int find(int x){
	if(fa[x]==x)return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
void add(int x,int v){
	fa[x]=find(x-1);
	ans[lim]+=v;
	h.push(-v);
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
	{
		int a,s,c,x;
		scanf("%d%d%d%d",&a,&s,&c,&x);
		if(x==0)
		{
			if(s>=1)
			{
				vg.push_back((vegetable){a+s,1,0,lim*m});
				c-=1;
				//拆出额外收益 
			}
			if(c>=1)vg.push_back((vegetable){a,c,0,lim*m});
		}
		else
		{
			if(s>=1)
			{
				vg.push_back((vegetable){a+s,1,0,((c-1)/x+1)*m});
				c-=1;
				//拆出额外收益 
			}
			if(c>=1)
			{
				vg.push_back((vegetable){a,c/x*x,x,0});
				if(c%x!=0)vg.push_back((vegetable){a,c%x,0,(c/x+1)*m});
				//拆出不是整段的蔬菜 
			}
		}
	}
	for(int i=1;i<=lim*m;i++)
		fa[i]=i;
	sort(vg.begin(),vg.end(),cp);
	for(vegetable vgt:vg)
	{
		int v=vgt.v,c=vgt.c,x=vgt.x,l=vgt.l;
		if(x==0)
		{
			while(c>=1)
			{
				int tx=find(l);
				if(tx==0)break;
				add(tx,v);
				c-=1;
			}
		}
		else
		{
			for(int i=c/x;i>=1;i--)
			{
				//枚举同一周期的蔬菜段 
				bool tf=false;
				for(int j=1;j<=x;j++)
				{
					//枚举每段蔬菜的数量 
					int tx=find(i*m);
					if(tx==0)
					{
						tf=true;
						break;
					}
					add(tx,v);
				}
				if(tf)break;
			}
		}
	}
	for(int i=lim-1;i>=1;i--)
	{
		ans[i]=ans[i+1];
		for(int j=1;j<=m&&h.size()>i*m;j++)
		{
			ans[i]+=h.top();
			h.pop();
		}
	}
	//计算其它时间的答案 
	while(q--)
	{
		int k;
		scanf("%d",&k);
		printf("%lld\n",ans[k]);
	}
	return 0;
}