联赛模拟测试14 C. 开心的金明

题目描述

分析

我们会发现对于原材料，它既没有购买数量的限制，也没有存储数量的限制
那么我们就可以直接预处理出每一个月购买一个原材料的最小花费
对于电脑，我们可以开一个 (set)
把每一天生产电脑的花费和能够生产电脑的数量依次扔进去
每过一天，我们就给 (set) 里的元素整体加上当天存储电脑所需要的花费
如果 (set) 里的元素满足不了需求量，直接输出 (-1)
如果元素的数量大于仓库的限制，则把花费大的扔出去、

代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=1e6+5;
long long tot;
struct asd{
	int val,num;
	asd(){}
	asd(int aa,int bb){
		val=aa,num=bb;
	}
	bool operator < (const asd& A)const{
		return val<A.val;
	}
};
std::multiset<asd> s;
int n,yclhf[maxn],xql[maxn],dnhf[maxn],dnnum[maxn],dnad,totsiz;
int sumycl[maxn],sumdn[maxn],maxnum[maxn];
void qk(int mmax){
	while(!s.empty()){
		asd now=*--s.end();
		s.erase(--s.end());
		if(totsiz-now.num<mmax){
			now.num-=(totsiz-mmax);
			s.insert(now);
			totsiz=mmax;
			break;
		} else {
			totsiz-=now.num;
		}
	}
}
int main(){
	n=read();
	for(rg int i=1;i<=n;i++){
		yclhf[i]=read();
		xql[i]=read();
		dnhf[i]=read();
		dnnum[i]=read();
	}
	for(rg int i=2;i<=n;i++){
		maxnum[i]=read();
		sumycl[i]=read();
		sumdn[i]=read();
	}
	for(rg int i=2;i<=n;i++){
		yclhf[i]=std::min(yclhf[i],yclhf[i-1]+sumycl[i]);
	}
	for(rg int i=1;i<=n;i++){
		dnhf[i]+=yclhf[i];
	}
	rg int nowhf,nowsl,nowsum;
	for(rg int i=1;i<=n;i++){
		if(totsiz>maxnum[i]){
			qk(maxnum[i]);
		}
		dnad+=sumdn[i];
		s.insert(asd(dnhf[i]-dnad,dnnum[i]));
		totsiz+=dnnum[i];
		nowsum=0;
		while(!s.empty()){
			nowhf=s.begin()->val+dnad;
			nowsl=s.begin()->num;
			totsiz-=nowsl;
			s.erase(s.begin());
			if(nowsl+nowsum<=xql[i]){
				tot+=1LL*nowsl*nowhf;
				nowsum+=nowsl;
			} else {
				tot+=1LL*(xql[i]-nowsum)*nowhf;
				s.insert(asd(nowhf-dnad,nowsl-(xql[i]-nowsum)));
				totsiz+=(nowsl-(xql[i]-nowsum));
				nowsum=xql[i];
			}
			if(nowsum==xql[i]) break;
		}
		if(nowsum!=xql[i]){
			printf("-1
");
			return 0;
		}
	}
	printf("%lld
",tot);
	return 0;
}