Producing Snow

Producing Snow

题解：这道题暴力可以出答案，但是会tle

tle代码：

#include 

using namespace std;
const int maxn = 1e5 + 10;

int pile[maxn],snow[maxn];
int main() {
	int n,hurt;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&pile[i]);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&snow[i]);
//		pile[i]-=snow[i];
	}
	for(int i=1;i<=n;i++){
		int hurt=0;
		for(int j=1;j<=i;j++){
			if(pile[j]!=0&&pile[j]-snow[i]>=0){
				hurt+=snow[i];
				pile[j]-=snow[i];
			}
			else{
				hurt+=pile[j];
				pile[j]=0;
			}
		}
		printf("%d ",hurt);
	}
	return 0;
}

题解：

前缀和➕优先队列进行维护

具体细节在代码里推到过了

#include 
#include 
using namespace std;
const int maxn = 1e5 + 10;
//这一道题需要使用优先队列，去存储需要的量
long long pile[maxn],snow[maxn];
long long sumn[maxn];
int main() {
	int n;//优先队列的定义
	long long hurt=0;
	priority_queue,greater>q;
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&pile[i]);
//		sum[i]=sum[i-1]+pile[i];
	}
	sumn[0]=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&snow[i]);
		sumn[i]=sumn[i-1]+snow[i];
		
	}
	//如果从第一个开始看的话
	//pile[1];
	//第二个
	//pile[2]+snow[1];
	//第三个
	//pile[3]+snow[1]+snow[2];
	//对呀，因为第一次融化不会伤害第二堆雪
	for(int i=1;i<=n;i++){
		q.push(pile[i]+sumn[i-1]);//要把sumn[i-1]带进去，因为接下来减去的是前缀和，为什么不能放入单个？？？如
		hurt = q.size()*snow[i];//现在里面剩几堆就几个
		while(!q.empty()&&q.top()<=sumn[i]){//你不够 融化的时候，我就不管你，每次该剪就剪
			hurt += q.top()-sumn[i];
			q.pop();
		}
		printf("%lld",hurt);
		if(i!=n){
//			char c;
			printf("%c",' ');
		}
		else{
			printf("n");
		}
	}
	return 0;
}