我搬运我自己

原文地址

---

题目翻译

翻译

都是我自己手翻的，应该比机翻好一点吧，如果有什么问题还请指教。

思路

贪心即可。能不买饮料就不买饮料，如果第 $i$ 天一定要买，找到第 $i$ 天及以前没买过饮料的店中最便宜的一家买饮料，直到超过第 $i$ 天的目标。如果之前所有店都买过了，就是无解。此算法的正确性可以感性理解。

这个过程可以使用小根堆来优化。发现其他题解都是优先队列，那我就手写堆吧。

代码及细节

• 考虑到极限情况下，答案 $=\sum C_i\leq 10^{14}$，所以答案要开 long long。
• 手写堆不要打错了，（个人认为）比某区间数据结构还难调。

#include <cstdio>
using namespace std;

char chrd;
#define read(x){ \
	x=0;\
	chrd=getchar();\
	while(chrd<'0'||chrd>'9') chrd=getchar();\
	while(chrd>='0'&&chrd<='9'){\
		x=(x<<3)+(x<<1)+(chrd^48);\
		chrd=getchar();\
	}\
}
int tsw;
#define swap(x,y){tsw=x;x=y;y=tsw;}

// 以上是一些宏定义

int h[100005],sizh;
inline void add(int x){
	h[++sizh]=x;
	int now=sizh;
	while(now){
		if(h[now>>1]>h[now])swap(h[now],h[now>>1])
		else break;
		now>>=1;
	}
}

inline void pop(){
	swap(h[sizh],h[1]);sizh--;
	int now=1;
	while((now<<1)<=sizh){
		int son=now<<1;
		if(son+1<=sizh&&h[son+1]<h[son])son++;
		if(h[son]<h[now])swap(h[now],h[son])
		else break;
		now=son;
	}
}

// 以上是堆 

int x[100005],c[100005];

int main(){
	int n,k,a;
	read(n);read(k);
	for(int i=1;i<=n;i++) read(x[i]);
	read(a);
	for(int i=1;i<=n;i++) read(c[i]);
	long long sum=0;
	for(int i=1;i<=n;i++){
		add(c[i]);
		while(k<x[i]){
			if(sizh==0){
				printf("-1\n");
				return 0;
			}
			k+=a;
			sum+=h[1];
			pop();
		}
	}
	printf("%lld",sum);
	return 0;
}