「LOJ 2306」「NOI2017」蔬菜

发表于

小 N 是蔬菜仓库的管理员，负责设计蔬菜的销售方案。

在蔬菜仓库中，共存放有 nn 种蔬菜，小 N 需要根据不同蔬菜的特性，综合考虑各方面因素，设计合理的销售方案，以获得最多的收益。

在计算销售蔬菜的收益时，每销售一个单位第 ii 种蔬菜，就可以获得 aia_i 的收益。特别地，由于政策鼓励商家进行多样化销售，第一次销售第 ii 种蔬菜时，还会额外得到 sis_i 的额外收益。

在经营开始时，第 ii 种蔬菜的库存为 cic_i 个单位。然而，蔬菜的保鲜时间非常有限，一旦变质就不能进行销售，不过聪明的小 N 已 经计算出了每个单位蔬菜变质的时间：对于第 ii 种蔬菜，存在保鲜值 xix_i，每天结束时会有 xix_i 个单位的蔬菜变质，直到所有蔬菜都变质。（注意：每一单位蔬菜的变质时间是固定的，不随销售发生变化）

形式化地：对于所有的满足条件 d×xi≤cid\times x_i \leq c_i 的正整数 dd ，有 xix_i 个单位的蔬菜将在 第 dd 天结束时变质。 特别地，若 (d−1)×xi≤ci<d×xi(d-1)\times x_i \le c_i < d\times x_i ，则有 ci−(d−1)×xic_i-(d-1)\times x_i 单位的蔬菜将在第 dd 天结束时变质。

注意，当 xi=0x_i = 0 时，意味着这种蔬菜不会变质。 同时，每天销售的蔬菜，总量也是有限的，最多不能超过 mm 个单位。

现在，小 N 有 kk 个问题，想请你帮忙算一算。每个问题的形式都是：对于已知的 pjp_j ，如果需要销售 pjp_j 天，最多能获得多少收益？

Constraints

n,pj≤105n,p_j\leq 10^5 ， m≤10m\leq 10 ， 0<ai,ci≤1090 < a_i,c_i \leq 10^9 ， 0≤si,xi≤1090\leq s_i,x_i \leq 10^9

Solution

贪心可得，我们要尽量多地卖出收益高的，且尽量晚卖。对于一份蔬菜，拆成 ai+sia_i+s_i 和 aia_i 两种，并钦定第一种过期时间最晚。

对于所有的蔬菜，我们先按价格从大到小排序。按照顺序处理方式为：从过期的最后一天开始尽量卖出，如果当前天已经满了就再往前卖。使用并查集可以保证复杂度。

对于询问，考虑从第 xx 天到第 x−1x-1 天的转移，贪心地丢弃最便宜的，且份数为从第 xx 天开始卖出的蔬菜 −- 从第一天到第 x−1x-1 天的空隙。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=2e5+5;
int n,m,k,A,S,C,X,cnt,tmp;
int tot,mxd,id,res,cur,mn;
int Q[N],f[N],v[N],p[N],d[N];
LL ans,sum,t,emp[N],del[N],s[N];
struct node{int a,c,x,d;}a[N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
bool cmp(node a,node b){return a.a>b.a;}
int find(int t){return f[t]==t?t:f[t]=find(f[t]);}
void link(int x,int y){x=find(x);y=find(y);if(y!=x)f[y]=x;}
void modify(int id,int c,int a)
{
	ans+=1ll*c*a;v[tot]+=c;p[tot]=a;
	d[id]+=c;if(d[id]==m)link(id-1,id);
}
int main()
{
	n=read();m=read();k=read();
	for(int i=1;i<=n;i++)
	{
		A=read();S=read();C=read();X=read();
		a[++cnt]=(node){A+S,1,0,X?(C-1)/X+1:N};
		C--;if(C)a[++cnt]=(node){A,C,X,X?(C-1)/X+1:N};
	}
	for(int i=1;i<=k;i++)
		Q[i]=read(),mxd=max(mxd,Q[i]);
	sort(a+1,a+cnt+1,cmp);
	for(int i=1;i<=mxd;i++)f[i]=i;
	for(int i=1;i<=cnt;i++)
	{
		tot++;id=find(min(a[i].d,mxd));
		res=(id-1)*a[i].x;cur=a[i].c-res;
		while(id&&cur)
		{
			mn=min(m-d[id],cur);
			modify(id,mn,a[i].a);cur-=mn;
			tmp=id;id=find(id-1);tmp-=id;
			cur+=min(res,tmp*a[i].x);
			res-=min(res,tmp*a[i].x);
		}
		if(!find(mxd))break;
	}
	for(int i=1;i<=mxd;i++)emp[i]=emp[i-1]+m-d[i];
	for(int i=mxd;i>=1;i--)del[i]=max(0ll,sum-emp[i]),sum+=d[i];
	for(int i=mxd;i>=1;i--)
	{
		s[i]=ans;t=del[i-1]-del[i];
		while(t)
		{
			mn=min(t,1ll*v[tot]);ans-=1ll*mn*p[tot];
			t-=mn;v[tot]-=mn;if(!v[tot])tot--;
		}
	}
	for(int i=1;i<=k;i++)printf("%lld\n",s[Q[i]]);
	return 0;
}