列表

详情

NC20803. [NOI2017]蔬菜

描述

小 N 是蔬菜仓库的管理员，负责设计蔬菜的销售方案。 在蔬菜仓库中，共存放有 n 种蔬菜，小 N 需要根据不同蔬菜的特性，综合考虑各 方面因素，设计合理的销售方案，以获得最多的收益。 在计算销售蔬菜的收益时，每销售一个单位第 i 种蔬菜，就可以获得 ai 的收益。 特别地，由于政策鼓励商家进行多样化销售，第一次销售第 i 种蔬菜时，还会额外 得到 si 的额外收益。 在经营开始时，第 i 种蔬菜的库存为 ci 个单位。 然而，蔬菜的保鲜时间非常有限，一旦变质就不能进行销售，不过聪明的小 N 已 经计算出了每个单位蔬菜变质的时间：对于第 i 种蔬菜，存在保鲜值 xi，每天结束时会 有 xi 个单位的蔬菜变质，直到所有蔬菜都变质。（注意：每一单位蔬菜的变质时间是固 定的，不随销售发生变化） 形式化地：对于所有的满足条件 d × xi ≤ ci 的正整数 d ，有 xi 个单位的蔬菜将在 第 d 天结束时变质。 特别地，若 (d − 1) × xi ≤ ci < d × xi ，则有 ci − (d − 1) × xi 单位的蔬菜将在第 d 天 结束时变质。 注意，当 xi = 0 时，意味着这种蔬菜不会变质。 同时，每天销售的蔬菜总. 量. 也是有限的，最多不能超过 m 个单位。 现在，小 N 有 k 个问题，想请你帮忙算一算。每个问题的形式都是：对于已知的 pj，如果需要销售 pj 天，最多能获得多少收益？ 

输入描述

第一行包含三个正整数 n, m, k，分别表示蔬菜的种类数目、每天能售出蔬菜总量上
限、小 N 提出的问题的个数。
接下来 n 行，每行输入四个非负整数，描述一种蔬菜的特点，依次为 ai, si, ci, xi ，意义如上文所述。
接下来 k 行，每行输入一个非负整数 pj ，意义如上文所述。

输出描述

输出 k 行，每行包含一个整数，第 i 行的数表示第 i 个问题的答案

示例1

输入: 

2 3 2
3 3 3 3
2 5 8 3
1
3

输出: 

16
27

说明:

共有两种蔬菜：
销售第 1 种蔬菜时，每销售一单位可以获得的收益为 3 ，第一次销售这种蔬菜时，额外可以获得的收益为 3。这种蔬菜共有 3 个单位，均会在第一天结束时变质。
销售第 2 种蔬菜时，每销售一单位可以获得的收益为 2 ，第一次销售这种蔬菜时，额外可以获得的收益为 5。这种蔬菜共有 8 个单位，其中，有 3 单位在第一天结束时变质，3 单位在第二天结束时变质，2 单位在第三天结束时变质。
在只销售 1 天时，应当销售 2 单位的第一种蔬菜和 1 单位的第二种蔬菜。在这种情况下：销售第一种蔬菜的收益为 2 × 3 + 3 ；销售第二种蔬菜的收益为1 × 2 + 5 ；总共获得的收益为 (2 × 3 + 3) + (1 × 2 + 5) = 16 。
在只销售 3 天时，第一天应当销售 3 单位的第一种蔬菜，第二天应当销售 3 单位的第二种蔬菜（此时选择在第二天结束时会变质的 3 个单位出售），第三天销售 2 单位的第二种蔬菜。
在这种情况下：销售第一种蔬菜的收益为 3 × 3 + 3 ；销售第二种蔬菜的收益为(3 + 2) × 2 + 5 ；总共获得的收益为 (3 × 3 + 3) + [(3 + 2) × 2 + 5] = 27 。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 173ms, 内存消耗: 13268K, 提交时间: 2019-03-16 14:55:02 

#include<stdio.h>
#include<algorithm>
#include<queue>
#define ll long long
#define N 100005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
struct node{int val,id;};
bool operator<(node a,node b){return a.val<b.val;}
priority_queue<node>Q;
int sum,n,m,q,a[N],s[N],c[N],x[N],fa[N],cnt[N],qry[N],Max;
ll ans[N*10];
int GF(int x){return x==fa[x]?x:fa[x]=GF(fa[x]);}
int main()
{
	int i;_R(n);_R(m);_R(q);
	for(i=1;i<=n;i++)
	{
		_R(a[i]);_R(s[i]);_R(c[i]);_R(x[i]);
		Q.push((node){a[i]+s[i],i});
	}
	for(i=1;i<=q;i++)
	{
		_R(qry[i]);
		Max=max(Max,qry[i]);
	}
	for(i=1;i<=Max;i++)fa[i]=i,cnt[i]=m;
	while(Q.size())
	{
		node tmp=Q.top();Q.pop();
		int t=x[tmp.id]?(c[tmp.id]-1)/x[tmp.id]+1:Max;
		if(t>Max)t=Max;
		t=GF(t);if(!cnt[t])continue;
		cnt[t]--;sum++;c[tmp.id]--;
		if(!cnt[t])fa[t]=fa[t-1];
		ans[sum]=ans[sum-1]+tmp.val;
		if(c[tmp.id])Q.push((node){a[tmp.id],tmp.id});
	}
	for(i=1;i<=q;i++)printf("%lld\n",ans[min(sum,qry[i]*m)]);
}

上一题

© 2024 nowcoder.com